How to Use Backtracking to Generate All Permutations, Combinations, and Subsets

Backtracking generates permutations, combinations, and subsets by traversing a decision tree with a recursive template that tracks the current path, available choices, and termination conditions, using either a start index (for subsets/combinations) or a used array (for permutations) to control element reuse.

The fucking-algorithm repository by labuladong provides a systematic framework for solving these classic combinatorial problems using depth-first search (DFS). By understanding three core patterns—subsets with a start pointer, permutations with a used array, and combinations with unlimited reuse—you can solve the nine common variations (unique vs. duplicate elements × no-reuse vs. reuse × order-important vs. order-unimportant) with a single, adaptable skeleton.

The Universal Backtracking Framework

Every backtracking solution revolves around three components:

• Path: The sequence of choices already taken (the partial answer stored in the current recursion stack).
• Choice list: All possible next elements available at the current decision tree node.
• Termination condition: When the path satisfies problem-specific constraints (e.g., length equals k, sum equals target, or all elements are used).

As implemented in 算法思维系列/回溯算法详解修订版.md, the generic template is:

void backtrack(Path path, List<Choice> choices) {
    if (termination) {
        result.add(new LinkedList<>(path));
        return;
    }
    for (Choice c : choices) {
        // make a choice
        path.add(c);
        // prune / update state if necessary
        backtrack(path, nextChoices);
        // undo the choice
        path.removeLast();
    }
}

From this skeleton, three distinct families of problems emerge based on how you construct the choice list and when you terminate.

Pattern 1: Subsets and Combinations (Order Irrelevant)

When generating subsets or combinations, the order of elements does not matter, and each element can be used at most once. The decision tree branches on whether to include the current element, then moves forward to avoid reuse.

In 高频面试系列/子集排列组合.md (lines 46–60), the implementation uses a start index that monotonically increases:

void backtrack(int[] nums, int start) {
    res.add(new LinkedList<>(track));               // every node is a valid subset
    for (int i = start; i < nums.length; i++) {
        track.addLast(nums[i]);                     // choose
        backtrack(nums, i + 1);                     // only later elements can be chosen
        track.removeLast();                         // undo
    }
}

Handling Duplicates in Subsets

If the input contains duplicate numbers (e.g., [1,2,2]), you must prune repeated branches to avoid duplicate subsets. First sort the array, then skip equal neighbors using the condition from lines 66–71 of the same file:

if (i > start && nums[i] == nums[i - 1]) continue;

This ensures that within the same recursive level, identical elements are only processed once.

Pattern 2: Permutations (Order Matters)

For permutations, the order of elements matters, and each element can still be used only once. The decision tree allows picking any unused element at each level.

According to 算法思维系列/回溯算法详解修订版.md (lines 33–65), use a boolean[] used array to track which indices are already in the path:

void backtrack(int[] nums) {
    if (track.size() == nums.length) {
        res.add(new LinkedList<>(track));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;                     // skip used elements
        used[i] = true;
        track.addLast(nums[i]);                     // choose
        backtrack(nums);
        track.removeLast();                         // undo
        used[i] = false;
    }
}

Variations and Duplicate Handling

To generate k-length permutations, simply change the termination condition to track.size() == k while keeping the same recursion structure.

For permutations with duplicate elements, sort the array first, then apply the pruning rule (lines 14–17):

if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;

This condition skips a duplicate when the previous identical element has not been used, ensuring unique permutations only.

Pattern 3: Unlimited Element Reuse

In problems like combination sum, elements can be reused unlimited times. After picking an element at index i, you stay at index i rather than moving to i + 1.

From 算法思维系列/回溯算法详解修订版.md (lines 29–33):

void backtrack(int[] nums, int start) {
    for (int i = start; i < nums.length; i++) {
        track.addLast(nums[i]);                     // choose
        backtrack(nums, i);                         // i (not i+1) → element can be reused
        track.removeLast();                         // undo
    }
}

Combine this with a running sum and early termination when the sum exceeds the target to implement efficient pruning.

Complete Working Examples

Below are production-ready Java implementations from the repository.

All Subsets (Unique Elements)

class SubsetSolution {
    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> track = new LinkedList<>();

    public List<List<Integer>> subsets(int[] nums) {
        backtrack(nums, 0);
        return res;
    }

    void backtrack(int[] nums, int start) {
        res.add(new LinkedList<>(track));          // every node is a subset
        for (int i = start; i < nums.length; i++) {
            track.addLast(nums[i]);
            backtrack(nums, i + 1);
            track.removeLast();
        }
    }
}

Source: 高频面试系列/子集排列组合.md (lines 46–60)

All Permutations (Unique Elements)

class PermuteSolution {
    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> track = new LinkedList<>();
    boolean[] used;

    public List<List<Integer>> permute(int[] nums) {
        used = new boolean[nums.length];
        backtrack(nums);
        return res;
    }

    void backtrack(int[] nums) {
        if (track.size() == nums.length) {
            res.add(new LinkedList<>(track));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            used[i] = true;
            track.addLast(nums[i]);
            backtrack(nums);
            track.removeLast();
            used[i] = false;
        }
    }
}

Source: 算法思维系列/回溯算法详解修订版.md (lines 33–65)

Subsets with Duplicates

class SubsetDupSolution {
    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> track = new LinkedList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);                         // bring duplicates together
        backtrack(nums, 0);
        return res;
    }

    void backtrack(int[] nums, int start) {
        res.add(new LinkedList<>(track));
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i - 1]) continue; // prune
            track.addLast(nums[i]);
            backtrack(nums, i + 1);
            track.removeLast();
        }
    }
}

Source: 高频面试系列/子集排列组合.md (lines 66–71)

Combination Sum (Unlimited Reuse)

class CombinationSumSolution {
    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> track = new LinkedList<>();
    int sum = 0;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backtrack(candidates, 0, target);
        return res;
    }

    void backtrack(int[] nums, int start, int target) {
        if (sum == target) {
            res.add(new LinkedList<>(track));
            return;
        }
        if (sum > target) return;

        for (int i = start; i < nums.length; i++) {
            sum += nums[i];
            track.addLast(nums[i]);
            backtrack(nums, i, target);            // i (not i+1) → reuse allowed
            track.removeLast();
            sum -= nums[i];
        }
    }
}

Source: 算法思维系列/回溯算法详解修订版.md (lines 29–33)

Summary

• Backtracking is a DFS technique that builds solutions incrementally and abandons partial candidates ("prunes") when they cannot possibly lead to valid solutions.
• Use a start index for subsets and combinations to prevent reuse of previous elements and avoid permutation duplicates.
• Use a used array for permutations to track which elements are currently in the path, allowing any unused element to be chosen next.
• Allow unlimited reuse by passing i (not i + 1) to the next recursive call, keeping the same element available for subsequent choices.
• Handle duplicate inputs by sorting first, then skipping equal neighbors using the i > start check for subsets or the !used[i-1] check for permutations.

Frequently Asked Questions

What is the difference between the start index approach and the used array approach?

The start index approach (used in subsets and combinations) ensures that once you move past an element, you never consider it again in the current path, guaranteeing that [1,2] and [2,1] are treated as the same combination. The used array approach (used in permutations) allows you to pick any element that isn't currently in your path, making [1,2] and [2,1] distinct valid permutations.

How does backtracking handle duplicate elements to avoid duplicate results?

For subsets and combinations, sort the array first, then skip an element if it equals the previous element and i > start (meaning you're not at the first occurrence in the current recursion level). For permutations, sort the array and skip an element if it equals the previous element and the previous element is not currently used (!used[i-1]), ensuring you only use duplicates in a specific order.

Can I use these patterns for problems with constraints like target sums or fixed-length outputs?

Yes. For target sum problems (like Combination Sum), maintain a running total and terminate the recursion when the sum equals or exceeds the target. For fixed-length outputs (like permutations of size k or combinations of size k), modify the termination condition to check if track.size() == k instead of checking if all elements are used or the end of the array is reached.

Why is every node in the subset recursion tree considered a valid result?

In subset problems, every decision (including the decision to take no further elements) represents a valid subset. By recording the current track at the beginning of each backtrack call before the loop iterates, you capture the empty set, single elements, and all intermediate combinations, not just the leaf nodes of maximum depth.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}