Subsets & Combinations

1. Introduction: The Power Set

Imagine you are at a salad bar with exactly three toppings: Tomatoes, Olives, and Croutons. You can choose any combination of these to put on your salad.

• You could choose none of them (an empty set).
• You could choose just Tomatoes.
• You could choose Tomatoes and Croutons.
• You could choose all three.

In mathematics, this is called the Power Set—the set of all possible subsets of a given set. For a set of $N$ items, there are exactly $2^N$ possible subsets.

In technical interviews, generating Subsets and Combinations is a fundamental application of the Backtracking pattern. While permutations focus on rearranging elements where order matters ([1, 2] vs [2, 1]), combinations and subsets focus on selecting elements where order does not matter ([1, 2] is identical to [2, 1], so we only generate one of them).

2. Core Concept: The "Include / Exclude" Decision Tree

To generate subsets without generating duplicates like [2, 1], we must enforce a strict direction: we only move forward. At any given index i in our array, we make a binary choice:

1. Include the element at i in our current subset.
2. Exclude the element at i from our current subset.

Alternatively, we can use a for loop starting from index to the end of the array, picking one element, and recursively calling the function with i + 1. Both conceptual models result in the exact same $2^N$ subsets.

3. Beginner Code Example: Subsets (Power Set)

Problem Statement: (LeetCode 78) Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets.

import java.util.ArrayList;
import java.util.List;

public class SubsetsBasic {
    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), nums, 0);
        return result;
    }
    
    private static void backtrack(List<List<Integer>> result, List<Integer> current, int[] nums, int start) {
        // Every state we reach is a valid subset! Add it immediately.
        result.add(new ArrayList<>(current));
        
        // Loop through the remaining choices
        for (int i = start; i < nums.length; i++) {
            // MAKE CHOICE: Include nums[i]
            current.add(nums[i]);
            
            // RECURSE: Move to the next index to prevent reusing elements 
            // and to maintain strict forward order.
            backtrack(result, current, nums, i + 1);
            
            // UNDO CHOICE: Exclude nums[i] (Backtrack)
            current.remove(current.size() - 1);
        }
    }
}

Complexity Analysis:

• Time Complexity: $O(N \times 2^N)$. There are $2^N$ subsets. Deep copying each subset to the result takes $O(N)$ time on average.
• Space Complexity: $O(N)$. The recursion stack goes $N$ levels deep, and the current list stores at most $N$ elements.

4. Intermediate Code Example: Subsets II (Handling Duplicates)

Problem Statement: (LeetCode 90) Given an integer array nums that may contain duplicates, return all possible subsets. The solution set must not contain duplicate subsets.

If the input is [1, 2, 2], the standard algorithm will generate [1, 2] twice (once using the first 2, and once using the second 2).

The Fix:

1. Sort the array so duplicates are adjacent.
2. In the for loop, skip the element if it is the same as the previous element in the current loop iteration.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SubsetsUnique {
    public static List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums); // 1. Sort to group duplicates
        backtrack(result, new ArrayList<>(), nums, 0);
        return result;
    }
    
    private static void backtrack(List<List<Integer>> result, List<Integer> current, int[] nums, int start) {
        result.add(new ArrayList<>(current));
        
        for (int i = start; i < nums.length; i++) {
            // 2. Prune duplicates:
            // If i > start, it means we already explored branches starting with nums[i-1] 
            // at this depth. Since nums[i] == nums[i-1], exploring nums[i] again is redundant!
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            
            current.add(nums[i]);
            backtrack(result, current, nums, i + 1);
            current.remove(current.size() - 1);
        }
    }
}

5. Advanced Code Example: Combination Sum

Problem Statement: (LeetCode 39) Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may choose the same number from candidates an unlimited number of times.

This changes the rules. We can reuse elements, but we still want to avoid duplicate combinations like [2, 2, 3] and [3, 2, 2].

The Insight: To reuse elements but avoid duplicate sets, when we make a choice i, we pass i into the recursion instead of i + 1. This allows the algorithm to pick the same number again, but prevents it from going backwards to pick numbers it already skipped!

import java.util.ArrayList;
import java.util.List;

public class CombinationSumClassic {
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), candidates, target, 0);
        return result;
    }
    
    private static void backtrack(List<List<Integer>> result, List<Integer> current, int[] candidates, int remain, int start) {
        // Base Case 1: Target overshot, invalid branch
        if (remain < 0) return;
        
        // Base Case 2: Target perfectly hit, valid combination!
        if (remain == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
        
        for (int i = start; i < candidates.length; i++) {
            current.add(candidates[i]);
            
            // RECURSE: Note we pass 'i', NOT 'i + 1' because we can reuse elements!
            // We pass remain - candidates[i] to track our sum.
            backtrack(result, current, candidates, remain - candidates[i], i);
            
            current.remove(current.size() - 1);
        }
    }
}

Complexity Analysis:

• Time Complexity: Roughly $O(N^{\frac{T}{M}})$, where $N$ is the number of candidates, $T$ is the target, and $M$ is the minimum value in candidates. The tree depth can be at most $T/M$.
• Space Complexity: $O(\frac{T}{M})$ for the recursion stack.

6. Common Mistakes Beginners Make

1. Confusing Permutations and Combinations state

   • The Mistake: Using a visited array when solving Subsets/Combinations.
   • Why it's wrong: A visited array allows you to go backwards in the array to pick numbers you missed (generating [2, 1]). Subsets only move strictly forward to prevent permutations.
   • The Fix: Use the start index variable to restrict the for loop to only look at elements $\ge$ start.

2. Passing start + 1 instead of i + 1

   • The Mistake: Writing backtrack(..., start + 1) inside the for-loop.
   • Why it's wrong: start doesn't change inside the loop. If start = 0, and the loop is at i = 3, passing start + 1 passes 1, allowing the recursion to pick indices 1 and 2 again!
   • The Fix: Always pass i + 1 (or i if reuse is allowed).

3. Pruning Duplicates without sorting

   • The Mistake: Applying if (i > start && nums[i] == nums[i-1]) on an unsorted array.
   • Why it's wrong: If the array is [2, 1, 2], nums[2] == nums[1] is false, so it doesn't skip the second 2, resulting in duplicate sets. Always sort first!

7. Interview Q&A

Q1: What's the difference between Combination Sum I, II, and III? Answer:

• Comb Sum I: Unlimited reuse of elements. (Pass i to recursion).
• Comb Sum II: Elements can only be used once, and input contains duplicates. (Sort, pass i + 1, and use nums[i] == nums[i-1] skip logic).
• Comb Sum III: Use exactly $K$ numbers from 1 to 9 that sum to $N$. (Pass i + 1, loop from start to 9, and add base case if (current.size() == k)).

Q2: Is there a way to generate subsets without recursion? Answer: Yes! We can use Bit Manipulation. An array of size $N$ has $2^N$ subsets. If we loop an integer mask from $0$ to $2^N - 1$, the binary representation of mask exactly maps to a subset. (e.g., 101 means include the 1st and 3rd elements, skip the 2nd). This is iteratively generating subsets in $O(N \times 2^N)$.

Q3: When should I use Bitmask Subsets vs Recursive Backtracking Subsets? Answer: If you just need the pure power set without constraints, Bitmask is often faster to write and execute. However, if the problem involves complex constraints (like stopping early if a sum exceeds a target), Recursive Backtracking is vastly superior because you can prune branches, whereas Bitmask forces you to generate every subset blindly.

8. Practice Problems

1. Subsets (LeetCode 78)
   • Goal: Generate the power set using backtracking.
2. Combination Sum II (LeetCode 40)
   • Goal: Find combinations summing to a target, using each number once, handling duplicates.
3. Combinations (LeetCode 77)
   • Goal: Generate all combinations of $K$ numbers from 1 to $N$.

9. Summary

• Directionality: Subsets and Combinations strictly move left-to-right through the input space to prevent generating duplicate permutations.
• The start parameter: The mechanism that enforces the left-to-right rule.
• Reuse: Passing i + 1 into recursion prevents reuse. Passing i allows unlimited reuse.
• Deep Copy: Always new ArrayList<>(current) when adding to your result list, otherwise you'll end up with empty lists as the backtrack unravels.