Subsets vs permutations

Two backtracking shapes look similar but answer different questions. Knowing which you need — and how their decision trees differ — is half the battle.

Subsets: "which elements?"

A subset is a choice of which elements to include; order doesn't matter. For each element you make a binary decision: in or out.

Decision tree: at depth i, branch on "include nums[i]?"
Count: 2ⁿ subsets.
[1,2,3] → {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} (8 of them).

// include/exclude each element
function subsets(i, current):
    if i == length(nums): record(current); return
    subsets(i+1, current)              // exclude nums[i]
    subsets(i+1, current + [nums[i]])  // include nums[i]

Permutations: "in what order?"

A permutation uses all elements but in some order; order is the whole point. At each slot you choose which unused element goes next.

Decision tree: at each depth, branch on "which remaining element next?"
Count: n! permutations.
[1,2,3] → 123, 132, 213, 231, 312, 321 (6 of them).

function permute(current, remaining):
    if length(remaining) == 0: record(current); return
    for each elem in remaining:
        permute(current + [elem], remaining without elem)

Combinations: "which k elements?"

A combination is a subset of a fixed size k — choose exactly k elements, order irrelevant ({1,2} and {2,1} are the same combination). It sits between subsets and permutations: like subsets, order doesn't matter; unlike subsets, the size is pinned.

Decision tree: same include/exclude shape as subsets, but only record a branch once it has chosen exactly k elements (prune branches that can no longer reach k).
Count: C(n, k) = n! / (k!·(n−k)!) combinations — e.g. choosing 2 of [1,2,3] gives {1,2}, {1,3}, {2,3} (3 of them).

The tell

"Choose some of these" / "any subset" → subsets (2ⁿ).
"Arrange all of these" / "every ordering" → permutations (n!).
"Choose exactly k, order doesn't matter" → combinations (C(n, k)).

Same backtracking skeleton, different branching rule. Spot which question is being asked and pick the matching tree.