The Three Backtracking Archetypes: Subsets, Permutations, and Combinations

Core Distinctions

Subsets      → Elements used once, Order DOES NOT matter, Each element is optional.
Combinations → Elements used once, Order DOES NOT matter, Result must be size K.
Permutations → Elements used once, Order DOES matter, Select from remaining pool.

The fundamental choice that differentiates these patterns is whether you care about order and whether you have a fixed size requirement.

The Universal Backbone

void backtrack(candidates, start, currentPath) {
    if (isGoalMet) {
        result.add(new ArrayList<>(currentPath)); // Copy!
        return;
    }
    
    for (int i = start; i < candidates.length; i++) {
        // Pruning logic here
        
        currentPath.add(candidates[i]); // Action
        backtrack(candidates, i + 1, currentPath); // Recurse (i + 1 or i)
        currentPath.removeLast(); // Undo
    }
}

1. Subsets (LeetCode 78)

Distinct elements, generate every possible power set.

void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
    // Collect the current state as a valid subset BEFORE the loop
    res.add(new ArrayList<>(path)); 
    
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        backtrack(nums, i + 1, path, res); // i + 1: cannot reuse the same index
        path.removeLast();
    }
}

Subsets with Duplicates (LeetCode 90)

Sort the input first, then skip siblings with duplicate values.

void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> res) {
    res.add(new ArrayList<>(path));
    for (int i = start; i < nums.length; i++) {
        // Horizontal pruning: Only pick the first instance among duplicates at this level
        if (i > start && nums[i] == nums[i - 1]) continue; 
        
        path.add(nums[i]);
        backtrack(nums, i + 1, path, res);
        path.removeLast();
    }
}

2. Combinations (LeetCode 77)

Find all possible combinations of size $k$ from $1 \dots n$.

void backtrack(int start, int n, int k, List<Integer> path) {
    if (path.size() == k) {
        res.add(new ArrayList<>(path));
        return;
    }
    
    // Pruning: Stop if there aren't enough numbers left to reach size K
    for (int i = start; i <= n - (k - path.size()) + 1; i++) {
        path.add(i);
        backtrack(i + 1, n, k, path);
        path.removeLast();
    }
}

3. Combination Sum (LeetCode 39)

Elements can be reused indefinitely to reach a target sum.

void backtrack(int[] candidates, int start, int remain, List<Integer> path) {
    if (remain == 0) {
        res.add(new ArrayList<>(path));
        return;
    }
    
    for (int i = start; i < candidates.length; i++) {
        // Assuming sorted: current is too big, so all subsequent i will also be too big
        if (candidates[i] > remain) break; 
        
        path.add(candidates[i]);
        // Note: pass 'i', not 'i + 1' to allow re-using the same element
        backtrack(candidates, i, remain - candidates[i], path);
        path.removeLast();
    }
}

Quick Reference Summary