Backtracking Concept and Decision Tree Visualization in DSA Typescript

Mental Model

Backtracking tries choices one by one and goes back if a choice leads to a dead end.

Analogy: Imagine walking in a maze and choosing paths. If a path is blocked, you return to the last junction and try a different path.

Start
  ↓
Choice 1 -> Dead end
  ↓
Backtrack ← Choice 2 -> Success

Dry Run Walkthrough

Input: Find all subsets of [1, 2] using backtracking

Goal: Generate all possible subsets by choosing or skipping each element

Step 1: Start with empty subset [] at index 0

[] ↑ (index 0)

Why: We begin with no elements chosen

Step 2: Choose element 1, subset becomes [1], move to index 1

[1] ↑ (index 1)

Why: Try including first element

Step 3: Choose element 2, subset becomes [1, 2], move to index 2 (end)

[1, 2] ↑ (index 2)

Why: Try including second element

Step 4: Reached end, record subset [1, 2], backtrack to index 1

[1, 2] (recorded), back to [1] ↑ (index 1)

Why: Save current subset and try skipping element 2

Step 5: Skip element 2, subset stays [1], move to index 2 (end)

[1] ↑ (index 2)

Why: Try skipping second element

Step 6: Reached end, record subset [1], backtrack to index 0

[1] (recorded), back to [] ↑ (index 0)

Why: Save current subset and try skipping element 1

Step 7: Skip element 1, subset stays [], move to index 1

[] ↑ (index 1)

Why: Try skipping first element

Step 8: Choose element 2, subset becomes [2], move to index 2 (end)

[2] ↑ (index 2)

Why: Try including second element after skipping first

Step 9: Reached end, record subset [2], backtrack to index 1

[2] (recorded), back to [] ↑ (index 1)

Why: Save current subset and try skipping element 2

Step 10: Skip element 2, subset stays [], move to index 2 (end)

[] ↑ (index 2)

Why: Try skipping second element

Step 11: Reached end, record subset [], backtrack complete

[] (recorded)

Why: Save empty subset, all choices tried

Result:

All subsets recorded: []
[1]
[1, 2]
[2]

Annotated Code

DSA Typescript

class Backtracking {
  subsets(nums: number[]): number[][] {
    const result: number[][] = [];
    const subset: number[] = [];

    function backtrack(index: number) {
      if (index === nums.length) {
        result.push([...subset]); // record current subset
        return;
      }

      // Choose nums[index]
      subset.push(nums[index]);
      backtrack(index + 1); // move to next element

      // Backtrack: remove last choice
      subset.pop();

      // Skip nums[index]
      backtrack(index + 1); // move to next element
    }

    backtrack(0);
    return result;
  }
}

const bt = new Backtracking();
const input = [1, 2];
const output = bt.subsets(input);
for (const s of output) {
  console.log(s);
}

if (index === nums.length) { result.push([...subset]); return; }

record current subset when reached end of array

subset.push(nums[index]); backtrack(index + 1);

choose current element and move forward

subset.pop();

undo choice to try skipping element

backtrack(index + 1);

skip current element and move forward

Output

[1, 2]

[1]

[2]

[]

Complexity Analysis

Time: O(2^n) because each element has two choices: include or skip, leading to 2^n subsets

Space: O(n) for recursion stack and subset storage during backtracking

vs Alternative: Compared to iterative subset generation, backtracking is more intuitive and easier to extend for constraints but has similar exponential time

Edge Cases

empty input array

returns [[]] as the only subset

DSA Typescript

if (index === nums.length) { result.push([...subset]); return; }

single element array

returns subsets with and without the element

DSA Typescript

subset.push(nums[index]); backtrack(index + 1);

When to Use This Pattern

When you see a problem asking for all combinations or subsets and need to explore choices step-by-step, use backtracking to try options and undo them if needed.

Common Mistakes

Mistake: Not undoing the choice (missing subset.pop()), causing wrong subsets
Fix: Add subset.pop() after recursive call to backtrack to remove last choice

Mistake: Recording subsets before reaching the end of array
Fix: Only record subsets when index reaches nums.length

Summary

Backtracking tries all choices by exploring and undoing decisions to find all solutions.

Use it when you need to explore all combinations or permutations with constraints.

The key is to choose, explore deeper, then undo the choice to try other options.