Generating Permutations and Subsets

"Try every possible ordering" or "check every possible subset" comes up constantly — in brute-forcing a small combinatorial optimization, in enumerating candidate portfolios of $k$ names out of $n$, in generating test cases. The generation itself is a small, fixed set of recursive patterns; the part that actually matters is knowing how fast the count explodes, because that tells you the size of $n$ where "just enumerate them" stops being a plan.

The idea: one recursive choice per position, three variants

Permutations of $n$ distinct items: at each of $n$ positions, choose one of the remaining unused items, recurse, then un-choose it (classic backtracking). There are $n!$ permutations — $10! \approx 3.6$ million, $15!$ is already 1.3 trillion.

Subsets (the power set) of $n$ items: at each item, decide include-or-exclude, recurse either way. There are $2^n$ subsets — $2^{20} \approx 10^6$, $2^{40}$ is already 1 trillion. This is exactly the shape used by bitmask DP, where each subset is represented as an integer.

Combinations of size $k$ out of $n$: like subsets, but you stop once $k$ items are chosen and never reconsider earlier positions once passed, avoiding the same combination being generated in more than one order. The count is $\binom{n}{k} = \frac{n!}{k!(n-k)!}$, which is far smaller than $2^n$ when $k$ is far from $n/2$ — $\binom{20}{2}=190$ versus $2^{20}\approx 10^6$.

Worked example: subsets of [1, 2, 3]

Include-or-exclude on 1, then 2, then 3, backtracking-style: exclude 1 → exclude 2 → exclude 3 gives {}; exclude 1 → exclude 2 → include 3 gives {3}; exclude 1 → include 2 → exclude 3 gives {2}; exclude 1 → include 2 → include 3 gives {2,3}; and mirroring all four with 1 included gives {1}, {1,3}, {1,2}, {1,2,3}. Eight subsets total, matching $2^3=8$.

def subsets(nums):                 # O(2^n) time and output size
    result, partial = [], []
    def backtrack(i):
        if i == len(nums):
            result.append(partial.copy())
            return
        backtrack(i + 1)            # exclude nums[i]
        partial.append(nums[i])
        backtrack(i + 1)            # include nums[i]
        partial.pop()
    backtrack(0)
    return result

Where it shows up

Interview staples: permutations, subsets, subsets II (with duplicates — sort first, skip repeated siblings), combination sum, letter case permutation. Interviewers watch for whether you know the count before writing the recursion, since it signals you understand the complexity you're about to generate. On a desk, brute-forcing a small basket of $\le 20$ candidate assets for a discrete allocation problem, or enumerating feasible sub-portfolios under a cardinality constraint, both rely on the exact same generation patterns and the same awareness of when $n$ has grown too large to enumerate.