Decision Tree Recursion: DSA Problem-Solving Pattern

Recognition Cheat Sheet

If you see…	Think…
All subsets / subsequences	Pick / Not Pick
All combinations of size K	Loop + Start Index
All permutations	Loop + Used Array
Combination Sum	Repeated Selection
Need all possible choices	Decision Tree Recursion

Main Trigger

Need to explore all possibilities → Make a choice → Recurse → Undo

The Basic Idea

At every step, make a decision.

For a taste of the full tree, here is pick/skip on two items — every leaf is one subset:

Generate All Subsets

Enumerate every subset of n items with a pick/skip recursion.

Each element gets two choices — PICK (join the set) or SKIP (leave it out). Diving left then right fills a binary tree whose 2ⁿ leaves are exactly all subsets. This pick/skip framing generalizes to most combinatorial enumeration.

TREE VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        subsets(i, chosen):
                      
                        2
                          if i == len(items): output chosen
                      
                        3
                            return
                      
                        4
                          subsets(i+1, chosen + [items[i]])  // PICK
                      
                        5
                          subsets(i+1, chosen)               // SKIP

For subsets, there are two choices:

             [ ]
            /   \
         skip   pick
          /       \
        ...       ...

This creates a decision tree containing every possible subset.

1. Pick / Not Pick — Subsets

Use this when every element has two choices:

Take it
Don't take it

Java

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();

    backtrack(
        nums,
        0,
        new ArrayList<>(),
        result
    );

    return result;
}

private void backtrack(
        int[] nums,
        int index,
        List<Integer> path,
        List<List<Integer>> result) {

    if (index == nums.length) {
        result.add(new ArrayList<>(path));
        return;
    }

    // Don't pick
    backtrack(
        nums,
        index + 1,
        path,
        result
    );

    // Pick
    path.add(nums[index]);

    backtrack(
        nums,
        index + 1,
        path,
        result
    );

    // Undo
    path.remove(path.size() - 1);
}

def subsets(nums):
    result = []

    def backtrack(index, path):
        if index == len(nums):
            result.append(path[:])
            return

        # Don't pick
        backtrack(index + 1, path)

        # Pick
        path.append(nums[index])

        backtrack(index + 1, path)

        # Undo
        path.pop()

    backtrack(0, [])
    return result

void backtrack(vector<int>& nums, int index,
               vector<int>& path, vector<vector<int>>& result) {
    if (index == (int)nums.size()) {
        result.push_back(path);
        return;
    }

    // Don't pick
    backtrack(nums, index + 1, path, result);

    // Pick
    path.push_back(nums[index]);

    backtrack(nums, index + 1, path, result);

    // Undo
    path.pop_back();
}

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> result;
    backtrack(nums, 0, {}, result);
    return result;
}

function subsets(nums) {
  const result = [];

  function backtrack(index, path) {
    if (index === nums.length) {
      result.push([...path]);
      return;
    }

    // Don't pick
    backtrack(index + 1, path);

    // Pick
    path.push(nums[index]);

    backtrack(index + 1, path);

    // Undo
    path.pop();
  }

  backtrack(0, []);
  return result;
}

Pattern

Element
   ↓
Skip ─────→ recurse
   ↓
Take ─────→ recurse

Recognition

Every element has Pick / Not Pick → Subset Decision Tree

2. Multi-Choice — Combinations

Use this when you need to choose K elements from a range.

Example:

n = 4, k = 2

[1,2]
[1,3]
[1,4]
[2,3]
[2,4]
[3,4]

Java

public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> result = new ArrayList<>();

    backtrack(
        1,
        n,
        k,
        new ArrayList<>(),
        result
    );

    return result;
}

private void backtrack(
        int start,
        int n,
        int k,
        List<Integer> path,
        List<List<Integer>> result) {

    if (path.size() == k) {
        result.add(new ArrayList<>(path));
        return;
    }

    for (int i = start; i <= n; i++) {

        path.add(i);

        backtrack(
            i + 1,
            n,
            k,
            path,
            result
        );

        path.remove(path.size() - 1);
    }
}

def combine(n, k):
    result = []

    def backtrack(start, path):
        if len(path) == k:
            result.append(path[:])
            return

        for i in range(start, n + 1):

            path.append(i)

            backtrack(i + 1, path)

            path.pop()

    backtrack(1, [])
    return result

void backtrack(int start, int n, int k,
               vector<int>& path, vector<vector<int>>& result) {
    if ((int)path.size() == k) {
        result.push_back(path);
        return;
    }

    for (int i = start; i <= n; i++) {

        path.push_back(i);

        backtrack(i + 1, n, k, path, result);

        path.pop_back();
    }
}

vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> result;
    backtrack(1, n, k, {}, result);
    return result;
}

function combine(n, k) {
  const result = [];

  function backtrack(start, path) {
    if (path.length === k) {
      result.push([...path]);
      return;
    }

    for (let i = start; i <= n; i++) {

      path.push(i);

      backtrack(i + 1, path);

      path.pop();
    }
  }

  backtrack(1, []);
  return result;
}

Why `i + 1`?

It prevents reusing the same element:

Choose 1
  ↓
Next choices start at 2

So:

backtrack(i + 1, ...)

Recognition

Choose K different elements → Loop + Start Index

3. Permutations

Unlike combinations, order matters.

[1,2,3]

[1,2,3]
[1,3,2]
[2,1,3]
[2,3,1]
[3,1,2]
[3,2,1]

Java

public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();

    backtrack(
        nums,
        new boolean[nums.length],
        new ArrayList<>(),
        result
    );

    return result;
}

private void backtrack(
        int[] nums,
        boolean[] used,
        List<Integer> path,
        List<List<Integer>> result) {

    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path));
        return;
    }

    for (int i = 0; i < nums.length; i++) {

        if (used[i])
            continue;

        used[i] = true;
        path.add(nums[i]);

        backtrack(
            nums,
            used,
            path,
            result
        );

        path.remove(path.size() - 1);
        used[i] = false;
    }
}

def permute(nums):
    result = []

    def backtrack(used, path):
        if len(path) == len(nums):
            result.append(path[:])
            return

        for i in range(len(nums)):

            if used[i]:
                continue

            used[i] = True
            path.append(nums[i])

            backtrack(used, path)

            path.pop()
            used[i] = False

    backtrack([False] * len(nums), [])
    return result

void backtrack(vector<int>& nums, vector<bool>& used,
               vector<int>& path, vector<vector<int>>& result) {
    if ((int)path.size() == (int)nums.size()) {
        result.push_back(path);
        return;
    }

    for (int i = 0; i < (int)nums.size(); i++) {

        if (used[i])
            continue;

        used[i] = true;
        path.push_back(nums[i]);

        backtrack(nums, used, path, result);

        path.pop_back();
        used[i] = false;
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> result;
    backtrack(nums, vector<bool>(nums.size(), false), {}, result);
    return result;
}

function permute(nums) {
  const result = [];

  function backtrack(used, path) {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }

    for (let i = 0; i < nums.length; i++) {

      if (used[i])
        continue;

      used[i] = true;
      path.push(nums[i]);

      backtrack(used, path);

      path.pop();
      used[i] = false;
    }
  }

  backtrack(new Array(nums.length).fill(false), []);
  return result;
}

Key Difference

Combinations:

backtrack(i + 1, ...)

Permutations:

used[i]

because we can choose any unused element next.

Recognition

Order matters + use every element → Permutation Backtracking

4. Repeated Selection — Combination Sum

Sometimes an element can be selected multiple times.

Example:

candidates = [2,3,6,7]
target = 7

[2,2,3]
[7]

Java

public List<List<Integer>> combinationSum(
        int[] candidates,
        int target) {

    List<List<Integer>> result = new ArrayList<>();

    backtrack(
        candidates,
        target,
        0,
        new ArrayList<>(),
        result
    );

    return result;
}

private void backtrack(
        int[] nums,
        int target,
        int start,
        List<Integer> path,
        List<List<Integer>> result) {

    if (target == 0) {
        result.add(new ArrayList<>(path));
        return;
    }

    if (target < 0)
        return;

    for (int i = start; i < nums.length; i++) {

        path.add(nums[i]);

        // i instead of i + 1
        // allows the same element again
        backtrack(
            nums,
            target - nums[i],
            i,
            path,
            result
        );

        path.remove(path.size() - 1);
    }
}

def combination_sum(candidates, target):
    result = []

    def backtrack(target, start, path):

        if target == 0:
            result.append(path[:])
            return

        if target < 0:
            return

        for i in range(start, len(candidates)):

            path.append(candidates[i])

            # i instead of i + 1
            # allows the same element again
            backtrack(target - candidates[i], i, path)

            path.pop()

    backtrack(target, 0, [])
    return result

void backtrack(vector<int>& nums, int target, int start,
               vector<int>& path, vector<vector<int>>& result) {
    if (target == 0) {
        result.push_back(path);
        return;
    }

    if (target < 0)
        return;

    for (int i = start; i < (int)nums.size(); i++) {

        path.push_back(nums[i]);

        // i instead of i + 1
        // allows the same element again
        backtrack(nums, target - nums[i], i, path, result);

        path.pop_back();
    }
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> result;
    backtrack(candidates, target, 0, {}, result);
    return result;
}

function combinationSum(candidates, target) {
  const result = [];

  function backtrack(remaining, start, path) {

    if (remaining === 0) {
      result.push([...path]);
      return;
    }

    if (remaining < 0)
      return;

    for (let i = start; i < candidates.length; i++) {

      path.push(candidates[i]);

      // i instead of i + 1
      // allows the same element again
      backtrack(remaining - candidates[i], i, path);

      path.pop();
    }
  }

  backtrack(target, 0, []);
  return result;
}

Important Difference

No reuse:

backtrack(i + 1, ...)

Reuse allowed:

backtrack(i, ...)

Recognition

Same element can be selected repeatedly → Recurse with i

The Three Main Choices

Remember these:

Subsets
→ Pick / Not Pick

Combinations
→ Loop + i + 1

Permutations
→ Loop + used[]

Repeated Selection
→ Loop + i

Common Mistakes

1. Forgetting to undo

After recursion:

path.remove(path.size() - 1);

Without this, choices from one branch leak into another.

2. Saving the same list

Wrong:

result.add(path);

Correct:

result.add(new ArrayList<>(path));

3. Using the wrong next index

i + 1 → cannot reuse
i     → can reuse

4. Confusing combinations and permutations

Combinations:
[1,2] = [2,1]

Permutations:
[1,2] != [2,1]

If order doesn’t matter → combinations.

If order matters → permutations.

Pattern Summary

All subsets
→ Pick / Not Pick

Choose K
→ Loop + start

Order matters
→ used[]

Can reuse element
→ pass i

Cannot reuse element
→ pass i + 1

Quick Rule

Every backtracking problem is basically: Choose → Recurse → Undo.

⚠️ Animation & Content Notice

Decision Tree

Recognition Cheat Sheet

Main Trigger

The Basic Idea

⚠️ Animation & Content Notice

Generate All Subsets

1. Pick / Not Pick — Subsets

Java

Pattern

Recognition

2. Multi-Choice — Combinations

Java

Why `i + 1`?

Recognition

3. Permutations

Java

Key Difference

Recognition

4. Repeated Selection — Combination Sum

Java

Important Difference

Recognition

The Three Main Choices

Common Mistakes

1. Forgetting to undo

2. Saving the same list

3. Using the wrong next index

4. Confusing combinations and permutations

Pattern Summary

Quick Rule

Premium Content

My Private Notes

Earn Premium with Referrals

Recognition Cheat Sheet

Main Trigger

The Basic Idea

Generate All Subsets

1. Pick / Not Pick — Subsets

Java

Pattern

Recognition

2. Multi-Choice — Combinations

Java

Why i + 1?

Recognition

3. Permutations

Java

Key Difference

Recognition

4. Repeated Selection — Combination Sum

Java

Important Difference

Recognition

The Three Main Choices

Common Mistakes

1. Forgetting to undo

2. Saving the same list

3. Using the wrong next index

4. Confusing combinations and permutations

Pattern Summary

Quick Rule

Premium Content

My Private Notes

Why `i + 1`?