Classic Backtracking: Subsets & Permutations

The previous chapter traced the recursion tree for subsets by hand. This chapter turns that trace into a clean, reusable function, then applies the same three-step template to a related but distinct problem: permutations, where order matters and every element must appear exactly once.

Generating subsets is naturally framed as: for each remaining element, either include it in the current path or skip it, without ever reconsidering an element that came before. Passing `start` forward as `i + 1` is what enforces "never reconsider an earlier element," which is exactly why every subset is recorded once and never twice.

Permutations flip the constraint: instead of "never look backward," the rule is "use every element exactly once, in every possible order." That needs a different bookkeeping tool, a `used` array (or set) tracking which elements are already part of the current path, so the loop can skip anything already placed instead of restricting which index it starts from.

In subsets, every one of the n elements independently is either in a given subset or not, two choices per element, made independently, giving 2ⁿ total subsets. In permutations, the count is different because the choices are not independent: the first position can be any of n elements, the second position can be any of the remaining n - 1, the third any of the remaining n - 2, and so on down to 1, giving n × (n - 1) × (n - 2) × ... × 1 = n! total orderings. Both algorithms additionally spend O(n) time copying `path` into `result` at each valid solution, so the tight complexity is O(n · 2ⁿ) and O(n · n!) respectively, but the dominant, headline term everyone quotes is the count of solutions itself.

• -subsets(nums): 2ⁿ possible subsets, since each of n elements is independently in or out.
• -permutations_of(nums): n! possible orderings, since the number of remaining choices shrinks by one at every level of the recursion.
• -Both are worse than exponential growth can hide well for small n (n=10 gives 1,024 subsets but 3,628,800 permutations). Always sanity-check n before assuming a brute-force search will finish in reasonable time.