Backtracking

Combinations

Choose K items from N without caring about order. Use a start index to avoid duplicates: each recursive call only considers elements AFTER the last chosen one. This naturally prevents picking the same combination twice.

O(C(n,k))

O(k)

say this out loud

Order does not matter, so I pass a start index and only look forward, which is what stops the same set appearing in different orders.

How It Works

Combinations select k items from n where order is irrelevant, so the recursion must never generate the same group twice in different orders. The fix is a start index: each call loops from start to the end, and after choosing element i it recurses with start = i + 1, permanently ruling out earlier elements. Choose, recurse, un-choose, and when the path reaches length k, record a copy.

The start-index discipline means [2,3] is generated but [3,2] never is, eliminating duplicates by construction rather than by filtering. There are C(n, k) results, and each costs O(k) to copy, so total time is O(k * C(n, k)) with O(k) auxiliary space. One pruning step cuts dead branches early: if the remaining elements cannot fill the path to size k (i > n - (k - path.length) + 1), stop the loop, which dramatically trims the tree for large n.

Step-by-Step Visualization

Choose 2 from [1, 2, 3, 4]. There are 6 combinations

1/9

Code

Java

static List<List<Integer>> combine(int n, int k) {
  List<List<Integer>> result = new ArrayList<>();
  backtrack(n, k, 1, new ArrayList<>(), result);
  return result;
}

static void backtrack(int n, int k, int start, 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(n, k, i + 1, path, result);
    path.remove(path.size() - 1);
  }
}

Tips & Gotchas

1Use a start index to avoid duplicates

2Only look at elements at or after start index

3Stop when path length reaches k

Practice Problems

1Combinations
2Combination Sum
3Combination Sum II
4Combination Sum III
5Palindrome Partitioning

About the Backtracking Pattern

Systematically explore all possible solutions by making choices one at a time. If a choice leads to a dead end, undo it (backtrack) and try the next option. You are exploring a decision tree: go deep, come back up when stuck.

Key insight

Every recursive solution has: base case, recursive case, and combining step. For backtracking, add: make choice → recurse → undo choice. Prune early to avoid TLE.

Common Recursion Interview Problems

Subsets
Permutations
Combination Sum
N-Queens
Word Search
Generate Parentheses
Letter Combinations of Phone Number

Frequently Asked Questions

When does the recursive call pass i versus i + 1 as the next start?

Pass i + 1 when each element may be used at most once, as in plain combinations and Combination Sum II. Pass i when an element may be reused unlimited times, as in Combination Sum. The element stays eligible for its own subtree but earlier elements remain excluded, so duplicates still cannot arise.

What pruning makes combination search fast in practice?

Two standard cuts: stop the loop once remaining elements cannot complete a k-sized selection, and for sum-target problems on a sorted array, break as soon as the current candidate exceeds the remaining target. Both prune entire subtrees at O(1) cost per check.