Generate all subsets, combinations, and permutations by exploring every include/exclude decision in a backtracking tree.
The subsets and combinations pattern uses backtracking to systematically explore every way to select elements from a collection. At each element you face a binary decision: include it or skip it. This creates a decision tree whose leaves are the complete subsets.
For an array [1, 2, 3], each element gets a yes/no decision. The tree branches at every element, and every root-to-leaf path produces one subset.
Why a binary tree? Each element is either in the subset or not. For n elements, we make n binary decisions. The tree has 2^n leaves, each representing a unique subset. This is why the power set of n elements always has exactly 2^n members.
Look for these recognition signals in the problem statement. If you spot one, the subsets/combinations pattern is very likely the right approach.
"All subsets" or "power set"
"All combinations of size k"
"Combination sum" or "target sum"
"Permutations" or "all orderings"
The key clue: The problem asks you to enumerate all valid selections (not count them, not find the optimal one). When the answer is a list of lists, you almost certainly need backtracking with the subsets/combinations template.
For each element, branch into two paths: one that includes the current element in the subset, and one that skips it. When we reach the end of the array, the current path is a complete subset. No pruning is needed because every combination is valid.
We track a path array that builds up the current subset. At index i, we either add nums[i] to path or skip it, then recurse to i+1.
The subsets template becomes even more powerful with pruning. When the problem constrains which subsets are valid (e.g., exactly k elements, or elements summing to a target), we can cut off entire branches of the decision tree early.
Choose exactly 2 elements from [1, 2, 3, 4]. We prune when path.length == k (found a result) or when there are not enough remaining elements to reach size k.
Find all combinations that sum to 7. Elements can be reused. We prune when the running sum exceeds the target.
Choosing the variant: For subsets, collect every path at every leaf. For combinations of size k, only collect when path.length == k. For combination sum, only collect when the running total equals the target. The same backtracking skeleton handles all three by changing only the base case and pruning condition.
Here are the annotated templates for the three core variants. Each uses the same backtracking skeleton with a different pruning condition.
List<List<Integer>> subsets(int[] nums) { List<List<Integer>> result = new ArrayList<>(); backtrack(nums, 0, new ArrayList<>(), result); return result; } void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> result) { result.add(new ArrayList<>(path)); // every node is a valid subset for (int i = start; i < nums.length; i++) { path.add(nums[i]); // include nums[i] backtrack(nums, i + 1, path, result); // recurse path.remove(path.size() - 1); // undo (backtrack) } }
void combine(int[] nums, int start, int k, List<Integer> path, List<List<Integer>> result) { if (path.size() == k) { // reached desired size result.add(new ArrayList<>(path)); return; } for (int i = start; i < nums.length; i++) { // Pruning: not enough elements left to fill remaining slots if (nums.length - i < k - path.size()) break; path.add(nums[i]); combine(nums, i + 1, k, path, result); path.remove(path.size() - 1); } }
void comboSum(int[] cands, int start, int target, List<Integer> path, List<List<Integer>> res) { if (target == 0) { // found valid combination res.add(new ArrayList<>(path)); return; } for (int i = start; i < cands.length; i++) { if (cands[i] > target) break; // prune: exceeds target path.add(cands[i]); comboSum(cands, i, target - cands[i], path, res); // i, not i+1 (reuse) path.remove(path.size() - 1); } }
The three knobs to turn: (1) start = i vs i+1 controls whether elements can be reused. (2) The base case condition controls which paths are collected. (3) The pruning condition controls which branches are skipped. Master these three and you can solve any subsets/combinations problem.
Let us trace through the subsets algorithm on [1, 2, 3] step by step, showing the call stack and results as they accumulate.
The start parameter prevents duplicates by only considering elements at or after the current index.
| CALL | ACTION | PATH | RESULTS SO FAR |
|---|---|---|---|
| bt(0) | add path to result | [] | [ [] ] |
| bt(0) | i=0, add 1 | [1] | [ [], [1] ] |
| bt(1) | i=1, add 2 | [1,2] | [ [], [1], [1,2] ] |
| bt(2) | i=2, add 3 | [1,2,3] | ..., [1,2,3] |
| bt(3) | base case, return | [1,2,3] | backtrack: remove 3 |
| bt(2) | loop ends, return | [1,2] | backtrack: remove 2 |
| bt(1) | i=2, add 3 | [1,3] | ..., [1,3] |
| bt(0) | i=1, add 2 | [2] | ..., [2] |
| bt(2) | i=2, add 3 | [2,3] | ..., [2,3] |
| bt(0) | i=2, add 3 | [3] | ..., [3] |
Notice the pattern: Every node in the recursion tree adds its current path to the result before recursing. The start parameter ensures we only add elements with higher indices, which prevents generating duplicates like [2,1] when we already have [1,2].
These are the classic LeetCode problems that use the subsets and combinations pattern, listed in rough order of difficulty.
Practice tip: Start with #78 Subsets (the purest form of the pattern). Then tackle #90 Subsets II which adds duplicate handling. #77 and #39 add constraints (fixed size and target sum). Finally, #46 Permutations uses a different traversal order and #22 Generate Parentheses uses a creative pruning rule.
Enter an array and choose a mode. Step through the backtracking algorithm and watch the decision tree unfold, with partial results building up at each step.
There are 2^n subsets in total (each element is either included or not). For each subset, we copy it into the result list, which takes O(n) in the worst case. Total: O(n · 2^n).
Combinations C(n, k): The number of subsets of size k is C(n, k) = n! / (k!(n-k)!). Each subset copy costs O(k). Pruning makes the actual work proportional to the output size.
Permutations: There are n! permutations, each of length n. Total: O(n · n!).
The recursion stack goes at most n levels deep (one level per element). The path array holds at most n elements. Excluding the output space, the auxiliary space is O(n).
Output-sensitive complexity: These algorithms are inherently exponential because the output itself is exponential in size. There is no way to generate 2^n subsets faster than O(2^n). The backtracking approach is optimal in the sense that it generates each output item in O(n) amortized time with no wasted work (assuming proper pruning).
Include or skip = binary decision tree. Every subsets problem reduces to a tree where each level makes a yes/no decision about one element. The tree has 2^n leaves, each a unique subset.
The start index prevents duplicates. By only considering elements at index start or later, you ensure that [1,2] is generated but [2,1] is not. This is the key difference between subsets/combinations (order does not matter) and permutations (order matters).
Three knobs: reuse, base case, pruning. Pass i (allow reuse) vs i+1 (no reuse) for the next start index. Change the base case for what to collect. Add pruning to skip impossible branches early.
Handle duplicates by sorting + skip. For inputs with duplicate elements (like Subsets II), sort the array first, then skip consecutive equal elements at the same recursion level: if (i > start && nums[i] == nums[i-1]) continue;
Always copy before collecting. The path list is mutated during backtracking. When adding to the result, always create a copy: result.add(new ArrayList<>(path)). Forgetting this is the most common bug.