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)

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. A powerful 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]

C(4,2)6

1/3

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. Think of it as exploring a decision tree — you go deep, and 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.