Skip to main content
Code ScholarsCodeScholars

Advanced Algorithm Design · Algorithm Design

Backtracking Algorithm

Backtracking explores choices recursively, abandons paths that cannot work, and returns to try alternatives.

Enroll NowText UsContact Code ScholarsFull DSA Course

Student Focus

We teach students to draw the choice tree before writing recursive code.

Guided Lesson Notes

Understanding Backtracking Algorithm

Backtracking Algorithm focuses on algorithmic reasoning, correctness, and choosing the right structure before writing code. Backtracking explores choices recursively, abandons paths that cannot work, and returns to try alternatives.

Model: start with inputs and outputs, then decide what information must be remembered at each step.

Invariant: every step must preserve the meaning of the variables and move measurably closer to the goal.

Implementation: pseudocode, traces, helper functions, tests, and complexity checks.

Use Backtracking Algorithm when the problem is less about syntax and more about selecting a strategy that scales.

Visual Model

A small picture for Backtracking Algorithm

1

Model

2

Trace

3

Analyze

Key Ideas

  • Choice tree
  • Constraint checks
  • Undoing state

Practice Prompts

  • Generate all subsets of a small set.
  • Write a backtracking solver for a simple constraint puzzle.

Vocabulary

Terms students should be able to say clearly

Input

The data the algorithm receives.

Output

The result the algorithm must produce.

Precondition

A fact that must be true before the algorithm runs.

Correctness

Why the algorithm always returns the required answer.

Complexity

How time and memory grow with input size.

Tradeoff

A choice where improving one cost may worsen another.

Worked Example

Worked example: tracing Backtracking Algorithm

Trace a small input, focusing on choice tree.

  1. 1Write a small input where Backtracking Algorithm is clearly useful.
  2. 2Label the part of the input related to Choice tree.
  3. 3Perform one operation and explain which invariant is still true afterward.
  4. 4Run a second operation that touches an edge case, such as an empty side, duplicate value, boundary index, disconnected vertex, or tie.
  5. 5Finish by saying which operation dominates the runtime and why.

Complexity Check

Costs students should be able to explain

OperationTypical CostReason
Trace a small inputSmall nUse a tiny example to understand state changes before coding.
Implement the core ideaDepends on topicChoose data structures that match the operations you need.
Analyze growthBig-OExplain how work changes as the input gets larger.

Common Mistakes

What to watch while practicing

  • Coding before drawing the structure or state changes.
  • Forgetting the invariant that makes the algorithm correct.
  • Testing only the sample input and skipping boundary cases.
  • Giving Big-O without explaining which operation dominates the work.

Interview-Style Coding Problem

Backtracking Algorithm interview problem: Combination Sum Count

Interview medium

Problem

Given distinct candidate numbers and a target, count how many unique nondecreasing combinations sum to the target. A candidate may be reused.

Input

The first line contains n and target. The second line contains n distinct positive integers.

Output

Print the number of valid combinations.

Sample Input

4 7
2 3 6 7

Sample Output

2

Why the sample works

The valid combinations are 2 + 2 + 3 and 7.

Approach

  1. 1Sort candidates so recursive choices stay in nondecreasing order.
  2. 2At each step choose an index at or after the current index.
  3. 3Reuse the same index when the candidate can be picked again.
  4. 4Stop a branch when the remaining target becomes 0 or negative.

Exponential in the number of combinations, with pruning from sorting.

Java Solution

import java.util.*;

public class Main {
  static int[] candidates;

  static int countWays(int start, int remaining) {
    if (remaining == 0) return 1;
    int ways = 0;

    for (int i = start; i < candidates.length; i++) {
      if (candidates[i] > remaining) break;
      ways += countWays(i, remaining - candidates[i]);
    }

    return ways;
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int target = sc.nextInt();
    candidates = new int[n];
    for (int i = 0; i < n; i++) candidates[i] = sc.nextInt();

    Arrays.sort(candidates);
    System.out.println(countWays(0, target));
  }
}

Python Solution

n, target = map(int, input().split())
candidates = sorted(map(int, input().split()))

def count_ways(start, remaining):
    if remaining == 0:
        return 1

    ways = 0
    for i in range(start, n):
        if candidates[i] > remaining:
            break
        ways += count_ways(i, remaining - candidates[i])
    return ways

print(count_ways(0, target))

Practice Challenge

Make the idea your own

Create a two-minute explanation of Backtracking Algorithm: define it, trace one example, name one edge case, and give the runtime of the main operation.

Tutoring Connection

Need help with this topic?

Bring a question or code attempt to a tutoring session.

Reserve a Free SessionText UsOpen Online Compiler