Subsets — choose / explore / undo

Recognize it from

“Return all subsets / the power set.” “All combinations of size k” (add a cur.size() == k guard). Generate all ways to pick or skip each element. Partition into groups where each group is a subset.

What it actually does

The search tree’s nodes are partial lists. At the start of a call you copy cur into the answer — including the empty list on the first call. Then a for-loop tries each unused later index: append nums[i], recurse with start i+1 (so you never reuse that slot or go backward), then remove the last element. That remove is the undo. Without it, every sibling would see a dirty path.

Simple version is include/exclude at a single index (binary tree of depth n). Interview version is the start-index for-loop (n-ary tree). Same 2ⁿ subsets. The call stack holds the current path; you still need an explicit ArrayList because Java does not give you the path as a stack of values, only as frames plus whatever you mutated.

List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    dfs(0, nums, new ArrayList<>(), ans);
    return ans;
}

void dfs(int i, int[] nums, List<Integer> cur, List<List<Integer>> ans) {
    if (i == nums.length) {
        ans.add(new ArrayList<>(cur));        // copy: cur will be undone on the way up
        return;
    }
    cur.add(nums[i]);                         // choose
    dfs(i + 1, nums, cur, ans);               // explore with nums[i]
    cur.remove(cur.size() - 1);               // undo
    dfs(i + 1, nums, cur, ans);               // explore without nums[i]
}

List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    if (nums == null) return ans;
    dfs(0, nums, new ArrayList<>(), ans);
    return ans;
}

void dfs(int start, int[] nums, List<Integer> cur, List<List<Integer>> ans) {
    ans.add(new ArrayList<>(cur));            // every prefix is a subset, including []
    for (int i = start; i < nums.length; i++) {
        cur.add(nums[i]);                     // choose nums[i]
        dfs(i + 1, nums, cur, ans);           // only later indices — no reuse, no permuting
        cur.remove(cur.size() - 1);           // undo so the next i sees the old path
    }
}

Example 1 — simple

nums = [1, 2]. Every snapshot of cur using the interview start-index template (copy happens at the top of each call).

Answer: [], [1], [1, 2], [2] — four subsets, copies taken on calls A, B, C, D.

Example 2 — every step

nums = [1, 2, 3]. Every call, the live cur, and the moment a copy is added. Indent = depth.

Answer in copy order: [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]. That is all 2³ subsets. The simple include/exclude version yields the same set in a different order (it only copies at the leaves).

Permutations with used[]

Recognize it from

“All permutations of the array.” Next permutation (the single successor — different algo, same ordering idea). “Arrange n distinct items.” Anagrams of a string as permutations of characters.

What it actually does

A permutation is a path of length n that uses each index once. used[i] is true while nums[i] sits on the current path. At depth n you copy cur. At smaller depth you try every index whose bit is still false: mark, append, recurse, then unmark and remove. The call stack is the depth; used[] is the explicit “which values are already in this stack.”

Simple version swaps in the array (the suffix is “still unused”). Interview version uses used[] so the original array stays untouched — easier when you also skip duplicates (if (i > 0 && nums[i]==nums[i-1] && !used[i-1]) continue after sorting). This page’s examples have distinct numbers.

List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    dfs(0, nums, ans);
    return ans;
}

void dfs(int i, int[] nums, List<List<Integer>> ans) {
    if (i == nums.length) {
        List<Integer> row = new ArrayList<>();
        for (int x : nums) row.add(x);
        ans.add(row);
        return;
    }
    for (int j = i; j < nums.length; j++) {
        swap(nums, i, j);                     // choose nums[j] for position i
        dfs(i + 1, nums, ans);                // suffix i+1.. is the remaining unused
        swap(nums, i, j);                     // undo so the next j sees the old order
    }
}

void swap(int[] a, int i, int j) {
    int t = a[i]; a[i] = a[j]; a[j] = t;
}

List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    if (nums == null || nums.length == 0) return ans;
    dfs(nums, new boolean[nums.length], new ArrayList<>(), ans);
    return ans;
}

void dfs(int[] nums, boolean[] used, List<Integer> cur, List<List<Integer>> ans) {
    if (cur.size() == nums.length) {
        ans.add(new ArrayList<>(cur));        // copy a finished permutation
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;                // already on this path
        used[i] = true;                       // choose index i
        cur.add(nums[i]);
        dfs(nums, used, cur, ans);
        cur.remove(cur.size() - 1);           // undo value
        used[i] = false;                      // undo bit — sibling may take i
    }
}

Example 1 — simple

nums = [1, 2] with used[]. Bits written as 0/1 for false/true.

Answer: [1, 2], [2, 1].

Example 2 — every step

nums = [1, 2, 3]. Every depth shows the three used bits. Copies happen only at depth 3.

Answer: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]. At every depth-3 row the used bits are [1,1,1].

Combination sum — reuse vs 0/1

Recognize it from

“Combinations that add to target.” Coin change that must list the coins, not only the count. Partition an array into a subset with sum T (0/1: each number once). “Unlimited copies of each candidate” vs “each candidate used at most once.”

What it actually does

Same choose/explore/undo as subsets, plus a remaining sum. Unbounded (combination sum): after picking candidates[i] you recurse with the same i, so that value can be picked again. 0/1 (subset sum / combination sum II without duplicates): recurse with i+1 so that slot is spent. Always stop when remain is 0 (copy path) or negative (overshoot — undo).

Simple version is pick-or-skip at index i, and the pick branch passes i unchanged (reuse). Interview version sorts, then a for-loop from start; the recursive call passes i not i+1. Sorting lets you break when candidates[i] > remain. The dry-runs below also show the overshoot branch before that break, so you see the undo.

List<List<Integer>> combinationSum(int[] a, int target) {
    List<List<Integer>> ans = new ArrayList<>();
    dfs(0, target, a, new ArrayList<>(), ans);
    return ans;
}

void dfs(int i, int remain, int[] a, List<Integer> cur, List<List<Integer>> ans) {
    if (remain == 0) {
        ans.add(new ArrayList<>(cur));
        return;
    }
    if (i == a.length || remain < 0) return;  // overshoot or no candidates left
    cur.add(a[i]);
    dfs(i, remain - a[i], a, cur, ans);       // reuse i — unbounded knapsack
    cur.remove(cur.size() - 1);               // undo
    dfs(i + 1, remain, a, cur, ans);          // skip this value forever (0/1 on this index)
}

List<List<Integer>> combinationSum(int[] a, int target) {
    List<List<Integer>> ans = new ArrayList<>();
    if (a == null || a.length == 0) return ans;
    Arrays.sort(a);                           // so we can stop once a[i] > remain
    dfs(0, target, a, new ArrayList<>(), ans);
    return ans;
}

void dfs(int start, int remain, int[] a, List<Integer> cur, List<List<Integer>> ans) {
    if (remain == 0) {
        ans.add(new ArrayList<>(cur));
        return;
    }
    for (int i = start; i < a.length; i++) {
        if (a[i] > remain) break;             // later values are even larger
        cur.add(a[i]);
        dfs(i, remain - a[i], a, cur, ans);   // pass i, not i+1: reuse allowed
        cur.remove(cur.size() - 1);
    }
}

Example 1 — simple

candidates = [2, 3], target = 5. Interview start-index walk. After [2, 2] remain is 1, so another 2 is refused (overshoot) and that branch backtracks.

Answer: [2, 3] only. [3, 2] is the same combination; the start index forbids going backward to 2 after picking 3. The overshoot is [2, 2] then refusing another 2.

Example 2 — every step

candidates = [2, 3, 6, 7], target = 7. Every branch, including those that overshoot (shown as “would go negative,” which the a[i] > remain break catches). Sorted already.

Answer: [2, 2, 3] and [7]. The branches that die are [2,2,2] (remain 1), [2,3] (remain 2), [3,3] (remain 1), and [6] (remain 1). Each of those undoes and tries the next sibling.

If the spec were 0/1 (each index once), the pick would call dfs(i+1, remain - a[i]). Then [2, 2, 3] would be illegal unless 2 appeared twice in the input array.