Backtracking: Subsets & Choices

Description

"All subsets", "all combinations that add up to a target" and "how many subsets hit this sum" all ask about every way of choosing from a set, and there are 2^n of them. You can't write the nested loops ahead of time for an n you don't know. Backtracking makes the choosing systematic. Recursion walks a tree of decisions, one element at a time: choose, explore, then undo the choice. A single shared list holds the current path.

We'll go from simple to more technical:

1. The pattern: choose, explore, un-choose, and record a copy.
2. A second flavor: duplicates in the input, skipped with i > start.
3. Where enumeration shows up in production (configurations, test cases, search).
4. What breaks it: shared lists, missing un-choose, over-eager deduplication, no pruning.

The approach

// Decide in/out for each element: a binary tree of choices
int countSubsetsWithSum(int[] nums, int i, int remaining) {
    if (i == nums.length) return remaining == 0 ? 1 : 0;              // one complete subset
    return countSubsetsWithSum(nums, i + 1, remaining - nums[i])       // include nums[i]
         + countSubsetsWithSum(nums, i + 1, remaining);                // exclude nums[i]
}

// Build the subsets themselves: choose, explore, un-choose
void subsets(int[] nums, int start, List<Integer> current, List<List<Integer>> result) {
    result.add(new ArrayList<>(current));          // record a COPY - current keeps changing
    for (int i = start; i < nums.length; i++) {
        current.add(nums[i]);                      // choose
        subsets(nums, i + 1, current, result);     // explore: only later elements, so no repeats
        current.remove(current.size() - 1);        // un-choose before trying the next element
    }
}

# Decide in/out for each element: a binary tree of choices
def count_subsets_with_sum(nums: list[int], i: int, remaining: int) -> int:
    if i == len(nums):
        return 1 if remaining == 0 else 0                          # one complete subset
    return (count_subsets_with_sum(nums, i + 1, remaining - nums[i])   # include nums[i]
            + count_subsets_with_sum(nums, i + 1, remaining))          # exclude nums[i]


# Build the subsets themselves: choose, explore, un-choose
def subsets(nums: list[int], start: int, current: list[int], result: list[list[int]]) -> None:
    result.append(current[:])                  # record a COPY - current keeps changing
    for i in range(start, len(nums)):
        current.append(nums[i])                # choose
        subsets(nums, i + 1, current, result)  # explore: only later elements, so no repeats
        current.pop()                          # un-choose before trying the next element

Both shapes enumerate the same 2^n subsets. The loop version grows each subset by picking the next element from start onward, which keeps elements in index order and never produces the same subset twice. Every recursion needs its base case - here, running out of elements - or it never stops. Combination Sum is the same loop with one change: recursing with i instead of i + 1 lets the same element be chosen again.

A second flavor: duplicates in the input

With repeated values, two different index choices can build the same subset ([1, 2a] and [1, 2b]). Sort the input, then at each loop level skip a value equal to the one just tried at that level:

Arrays.sort(nums);
void subsetsWithDup(int[] nums, int start, List<Integer> current, List<List<Integer>> result) {
    result.add(new ArrayList<>(current));
    for (int i = start; i < nums.length; i++) {
        if (i > start && nums[i] == nums[i - 1]) continue;   // same value, same level: already covered
        current.add(nums[i]);
        subsetsWithDup(nums, i + 1, current, result);
        current.remove(current.size() - 1);
    }
}

def subsets_with_dup(nums: list[int], start: int, current: list[int], result: list[list[int]]) -> None:
    result.append(current[:])
    for i in range(start, len(nums)):
        if i > start and nums[i] == nums[i - 1]:
            continue                           # same value, same level: already covered
        current.append(nums[i])
        subsets_with_dup(nums, i + 1, current, result)
        current.pop()

# call it on sorted input: nums.sort()

i > start is the precise rule: the first copy of a value at a level is always allowed, so [2, 2] can still be built by taking the first 2 at one level and the second 2 one level deeper. Writing i > 0 also blocks that second 2 and loses [2, 2] and [1, 2, 2].

Where you'll see it

Test-matrix generation (which combinations of feature flags or configuration options to exercise), bundle and portfolio selection under a budget, and puzzle and scheduling solvers are backtracking over choices. Real systems keep them tractable with pruning, symmetry breaking and memoization, because the raw space doubles with every option.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. A subsets generator records results with result.add(current). What comes back for [1, 2, 3]?

2. Why is the duplicate check i > start rather than i > 0?

3. What single change turns "combinations using each element at most once" into Combination Sum (unlimited reuse)?

Key takeaways

• Backtracking walks a tree of choices with one shared working list: choose, explore, un-choose.
• Record a copy of the working list, never the list itself.
• Include/exclude gives 2^n subsets; the start-index loop enumerates them without repeats.
• With duplicate values: sort, then skip equal siblings with i > start.
• Prune as soon as a branch can't succeed; switch to DP when only a count is needed.