Subsets, Permutations, and Combinations

Intermediate · 9 min

One backtracking template generates every subset, permutation, and k-combination — plus the sort-and-skip trick for duplicate elements.

Before thisBacktracking

NeetCode · 9 min

Subsets, Permutations, and Combinations

The player loads from youtube-nocookie.com when you press play. Nothing reaches YouTube before that.

Taught by NeetCodeReport a problem with this video
Not started
Set this lesson's status

What you'll learn

  • Subsets, permutations, and k-combinations are all generated by the same recursive shape: build a partial candidate, recurse, then undo the last choice ("backtrack") and try the next option.
  • Subsets come from an include/exclude decision at every index: at each position you either add the current element to the running set or skip it, which naturally produces all 2^n subsets.
  • Permutations come from choosing, at each recursion level, which not-yet-used element goes next — tracked either with a "used" boolean array/set or by swapping the chosen element into the current position in place.
  • A combination of size k is the subsets tree pruned two ways: stop recursing once the running group hits size k, and never reconsider an index you've already passed, so the same pair is never built in two different orders.
  • Duplicate elements are handled by sorting first and then skipping any element that equals its immediate predecessor at the same recursion depth, which prunes identical branches without a visited-set lookup.
  • Skipping a duplicate only applies 'at the same level' of the tree — the same value is allowed to reappear one level deeper, since that represents using a later copy of it, not re-trying the same choice.

One recursion tree, three different questions

Subsets, permutations, and combinations look like three separate problems, but they’re the same backtracking skeleton answering three different questions about the same array. The skeleton is always: maintain a partial candidate (a path), make one choice, recurse one level deeper, then undo that choice before trying the next one. What changes between the three problems is which choices are legal at each step and when a partial candidate counts as a finished answer.

Subsets: include or exclude, at every index

To generate every subset of [1, 2, 3], walk the array index by index and make a binary decision at each one: include this element in the running subset, or don’t. At index 0 you branch into “with 1” and “without 1”; inside each of those branches, index 1 again branches into “with 2” / “without 2”; and so on. Every one of the 2³ = 8 leaves of that decision tree is a distinct subset: [1,2,3], [1,2], [1,3], [1], [2,3], [2], [3], []. Code-wise, this is: dfs(i) calls path.append(nums[i]); dfs(i+1); path.pop(); dfs(i+1) — append, recurse, pop (the “exclude” branch just skips the append). The pop is the backtrack step: it undoes the include so the exclude branch starts from a clean path.

Permutations: pick what’s still unused

Permutations need a different question at each level: not “include or exclude index i” but “which remaining element goes here next.” For [1, 2, 3], the first position can be filled by 1, 2, or 3; whichever is chosen, the second position is filled by one of the two remaining elements; the third position is forced. The standard implementation keeps a used array (or set) of indices already placed in the path — at each level, loop over every index not yet marked used, mark it, recurse, then unmark it (the backtrack). An equally common alternative swaps the chosen element into the current position of the array itself and swaps it back afterward, avoiding the extra used array entirely. Either way, the tree has n choices at the root, n−1 at the next level, down to 1, giving n! leaves.

Combinations: the subsets tree, pruned

A combination of size k is generated with the same include/exclude tree as subsets, with two prunings added. First, stop extending a branch — and record it as an answer — the moment the running group reaches size k, rather than running all the way to the end of the array. Second, each recursive call only considers indices after the last one used, never earlier ones. That second rule is what keeps combinations unordered: without it, the tree would independently build [1,2] and [2,1] as if they were different answers. For choose 2 from [1,2,3]: start at index 0, take 1, then recurse from index 1 to pick a second element (2 or 3) — giving [1,2] and [1,3]; back up, skip 1, take 2, recurse from index 2 — giving [2,3]. Three combinations total, matching C(3,2) = 3.

The duplicate problem: sort, then skip same-at-this-level

All three patterns break when the input has repeated values, because the tree above treats each index as distinct even when two indices hold the same value — so [2a, 2b] and [2b, 2a] get generated as if they were different results. The fix is always the same: sort the array first so equal values sit next to each other, then at any point where you’re choosing among several indices at the same recursion level, skip an index if it holds the same value as the index immediately before it and that previous index was already considered (not currently in the path) at this level. For subsets of [1, 2, 2] sorted: at the top level, after exploring the branch that includes the first 2, the branch that would include the second 2 is skipped, because it would just rebuild subsets already produced by the first one. Crucially, the second 2 is not banned deeper in the tree — once the first 2 is already in the path, using the second 2 right after it is how you build [2, 2] — the skip rule only fires between siblings at the same decision point, not between parent and child.

Check yourself

  1. 01Why does the include/exclude template for subsets never need a 'used' tracker the way permutations do?

    Because subsets only care about which elements end up in the set, not their order, so each index is visited exactly once moving forward through the array — there's nothing to mark as used since you never reconsider an earlier index.

  2. 02In the combinations template, why does the recursive call pass `i + 1` as the next starting index instead of 0?

    Because combinations are unordered, so once index i has been considered (included or not), re-starting from 0 would let a later branch rebuild the same group in a different order, producing duplicate combinations; always moving the start index forward guarantees each subset of indices is built exactly once.

  3. 03For input [1, 2, 2], why does sorting first make the 'skip duplicates' rule simple to implement?

    Sorting puts equal values adjacent to each other, so 'don't reuse the same value twice at this decision point' reduces to a single array check — compare the current element to the previous one and skip if they're equal and the previous one was already considered at this same level — rather than needing a hash set of values already tried at that level.

Go deeper

Notes

Private to you

Esc
↑↓ navigate↵ open? shortcuts

Keyboard shortcuts

Press Esc to close

Anywhere

⌘K
Search and commands
/
Search
?
This sheet
Esc
Close

Reading a lesson

J
Next lesson
K
Previous lesson
B
Bookmark