Subsets, permutations and combinations — LeetCode patterns

Problem

You are given a small collection and asked to list or count by listing every selection that fits a rule. The input size is tiny (usually 20 or fewer items) because the answer itself is exponential: a set of n items has 2ⁿ subsets and n! orderings, so no algorithm can print them faster than they exist. What matters is generating each exactly once, with no repeats, and without building thousands of throwaway copies.

Signal	Pattern	Why
"Return all subsets" or "the power set"	Include-or-skip recursion, or a loop from a start index	Every node of the search is itself an answer, and the start index prevents the same subset in a different order.
"All orderings" or "all arrangements"	Permutation search with a used marker	Order matters, so any unused item may come next.
"Choose k of n"	Combinations with a start index and an early stop	Order does not matter, and the path stops growing at length k.
"Input may contain duplicates, no repeated answers"	Sort, then skip a value equal to its left sibling	Two equal choices at the same depth lead to identical subtrees.
"Generate all valid strings of some shape"	Build character by character, offer only moves that keep the prefix valid	The rule is enforced while building, so dead prefixes are never extended.
"Maximum or minimum of something over all selections"	Dynamic programming if subproblems overlap	If you need one number rather than the list, listing everything is wasted work.

Intuition

Picture packing a bag from three items on a table. You decide about the first item, then the second, then the third. Each decision splits the future in two, so after three decisions you have visited every one of the eight possible bags. That is a tree of decisions, and backtracking is simply a walk over that tree.

The only trick is to use one shared bag instead of a new bag per branch. Put an item in, walk everything that can follow, then take the item back out. Taking it back out is the "backtrack" step, and it is what restores the bag to the state the parent expected. Whenever the search reaches a spot that counts as an answer, you copy the bag into the results, because the bag itself will keep changing.

Subsets and permutations are the same walk with different offers at each node. For subsets you only offer items after the last one you took, so {1, 2} is reached once rather than also as {2, 1}. For permutations you offer every item you have not used yet, so order creates distinct answers.

Each circle shows the item just added; the label beside it is the whole bag at that moment. Every node of the tree is a subset, so all 8 are recorded. The diagram scrolls sideways on a narrow screen.

Mechanics

The template in words

Keep a shared path list and a recursive function explore. On entry, decide whether the current path is an answer and, if so, copy it into the results. Then loop over the options that are legal here. For each one: append it to the path (choose), call explore (explore), pop it off again (unchoose).

The invariant

When explore returns, the path is exactly what it was when the call began. That holds by induction: each iteration of the loop pushes one item and pops one item, and the recursive call in between leaves the path unchanged by the same argument on a shorter remaining problem. Because of that invariant, the caller can keep looping without any cleanup, and the whole search uses one list for its path.

Why each answer appears exactly once

Every answer corresponds to one root-to-node path in the tree, and the tree is built so that path is unique. For subsets, the loop starts at start, so items are always taken in increasing position, which gives each subset one canonical order. For permutations, nothing is skipped except what is already on the path, so each distinct ordering of the input positions is exactly one path. Counting nodes confirms it: the subset tree has 2ⁿ nodes and the permutation tree has n! leaves.

Repeated values

If the input has equal values, two different choices at the same depth can produce the same subtree, and the answers repeat. Sort first so equal values sit together, then inside the loop skip index i when i > start and nums[i] == nums[i - 1]. The first of a run of equal values is allowed at any depth; a later one in the run may only be used after the earlier one is already on the path. That condition i > start is the whole subtlety: it says "this value was already offered to this parent".

Green leaves are complete permutations. Each level removes one item from the pool, so the fan-out is 3, then 2, then 1: 3! = 6 leaves in all.

Worked example

Generate every subset of 1, 2, 3. The search makes 8 calls to explore, one per subset, and records each on entry, in this order.

Call	Path on entry	Recorded
1	{}	{}
2	{1}	{1}
3	{1, 2}	{1, 2}
4	{1, 2, 3}	{1, 2, 3}
5	{1, 3}	{1, 3}
6	{2}	{2}
7	{2, 3}	{2, 3}
8	{3}	{3}

The same 3 items have 6 permutations, found after 16 calls (123, 132, 213, 231, 312, 321). Only the calls at full depth record an answer; the rest are interior nodes.

Duplicates. The input 2, 1, 2 sorts to 1, 2, 2. Without the skip rule the search yields 8 subsets, including repeats. With the skip rule it cuts 2 branches and yields 6 distinct subsets: {}, {1}, {1,2}, {1,2,2}, {2}, {2,2}.

Combinations. Choosing 2 of 1 to 4 gives 6 pairs (12, 13, 14, 23, 24, 34) in 10 calls. Without the early stop the loop would run all the way to 4 and make 11 calls; the stop skips starts that could not leave enough numbers to fill the path.

Parentheses. Three pairs give 5 well-formed strings (((())), (()()), (())(), ()(()), ()()()) after 22 calls. The rule "close only if something is open" prunes every invalid prefix before it is built.

Implementation

def subsets(nums):
    results, path = [], []

    def explore(start):
        results.append(path[:])          # every node is an answer; copy, because path keeps changing
        for i in range(start, len(nums)):
            path.append(nums[i])
            explore(i + 1)
            path.pop()

    explore(0)
    return results


def permutations(nums):
    results, path = [], []
    used = [False] * len(nums)

    def explore():
        if len(path) == len(nums):
            results.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            explore()
            path.pop()
            used[i] = False

    explore()
    return results

Variations and edge cases

def subsets_with_dup(nums):
    nums.sort()
    results, path = [], []

    def explore(start):
        results.append(path[:])
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue
            path.append(nums[i])
            explore(i + 1)
            path.pop()

    explore(0)
    return results


def combine(n, k):
    results, path = [], []

    def explore(start):
        if len(path) == k:
            results.append(path[:])
            return
        for value in range(start, n - (k - len(path)) + 2):
            path.append(value)
            explore(value + 1)
            path.pop()

    explore(1)
    return results


def generate_parentheses(n):
    results = []

    def explore(text, opened, closed):
        if len(text) == 2 * n:
            results.append(text)
            return
        if opened < n:
            explore(text + "(", opened + 1, closed)
        if closed < opened:
            explore(text + ")", opened, closed + 1)

    explore("", 0, 0)
    return results

Copying the path. results.append(path) stores a reference to the one shared list, which ends up empty. Always store path[:] or list(path).
Duplicates in permutations. Sort the input and, in the loop, skip index i if nums[i] == nums[i - 1] and nums[i - 1] is not currently used. That keeps equal values in their original relative order, so each distinct ordering is built once.
Start index versus used array. A start index is for choices where order does not matter (subsets, combinations); a used array is for orderings. Mixing them up either loses answers or repeats them.
Bitmask alternative. For subsets only, counting from 0 to 2ⁿ - 1 and reading the bits of each number enumerates all of them without recursion.
Edge cases: an empty input (one subset, the empty one; one permutation, the empty list), k equal to 0 or n, k greater than n (no answers), and a phone-digit style input where some choice lists are empty.

Complexity and tradeoffs

Time: proportional to the number of tree nodes times the cost of copying an answer. Subsets are O(n · 2ⁿ), permutations are O(n · n!), combinations of k from n are O(k · C(n, k)). Output size sets a floor you cannot beat.
Space: O(n) for the recursion stack and the shared path, not counting the results.
Baseline. Building a new list at every call is easier to write and costs an extra copy per node; the shared path with push and pop avoids that.
Pruning pays. For combinations, the early stop cut the calls from 11 to 10 for choosing 2 of 4, and the saving grows quickly with n. Stopping when no valid completion exists is the idea the next page builds on.
When it fails. If the input is large (say 30 items) or you need only a count, a maximum or a yes/no, enumerating everything is hopeless. Use dynamic programming or a formula instead.

Problems

Every home problem asks for the full list of selections. Sum of All Subset XOR Totals is the odd one out: it can be answered by listing subsets, which is the intended route here, but it also has a closed form that avoids the enumeration. Combination Sum and Combination Sum II appear below because they reuse the template; their home is the next page, where the sum limit becomes the pruning rule.

Easy

1863. Sum of All Subset XOR Totals NeetCode 250
Each bit set anywhere in the array appears in half of all subsets, so the total is the OR of all numbers times 2^(n-1).

Medium

17. Letter Combinations of a Phone Number Grind 169 NeetCode 150 NeetCode 250
Each digit offers a few letters, so a depth-first choice of one letter per digit enumerates exactly the cartesian product.
22. Generate Parentheses Grind 169 NeetCode 150 NeetCode 250
Build strings one character at a time, adding an opener while any remain and a closer only while it would still be balanced.
46. Permutations Grind 169 NeetCode 150 NeetCode 250
Grow a permutation one position at a time, choosing only from values not yet used on the current path.
47. Permutations II NeetCode 250
Sort, then at each position skip a value equal to its unused left neighbour, so duplicate permutations are never started.
77. Combinations NeetCode 250
Choose numbers in increasing order and stop a branch early when too few numbers remain to reach size k.
78. Subsets Grind 169 NeetCode 150 NeetCode 250
Each element is either in or out, so a binary decision tree of depth n, or the bitmasks 0..2^n-1, lists every subset.
90. Subsets II NeetCode 150 NeetCode 250
Sort, then skip an element equal to the one before it at the same depth, so each distinct subset is built once.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

Connections

Read first

Recursion and the call stack intro

Check yourself

Why must the results store a copy of the path?

The path is one shared list that the search keeps pushing to and popping from. Storing the list itself would store a reference, so every recorded answer would end up showing the final (empty) state. A copy freezes the contents at that moment.

How many calls does the subset search make for 3 items, and why?

8. Every call corresponds to exactly one subset, and there are 2³ of them, so the call count equals the number of answers.

What does the test i > start do in the duplicate-skipping rule?

It restricts the skip to siblings: values offered by the same parent. The first item in a run of equal values (at i == start) is always allowed, so 1, 2, 2 can still produce a subset with both 2s. Without that test, you would also skip a legitimate deeper use of the second 2 and lose answers.

Why is the early stop in combinations safe?

If fewer numbers remain than the path still needs, no completion can reach length k, so those branches contain no answers. Stopping there changed the calls from 11 to 10 for choosing 2 of 4 without changing the answers.

References

Skiena, The Algorithm Design Manual, chapter 9 on combinatorial search and backtracking, including generating subsets and permutations.
Sedgewick and Wayne, Algorithms, section 4.1 (depth-first search): backtracking is a depth-first search of the implicit decision tree, undoing each step on the way back.
Knuth, The Art of Computer Programming, volume 4A, sections 7.2.1.2 (generating all permutations) and 7.2.1.3 (generating all combinations).
Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, appendix C on counting and combinatorics.
The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.