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

> Master backtracking to generate all permutations combinations and subsets Learn the recursive template start index and used array techniques for efficient algorithm problem solving

- Repository: [DonglaiFu/fucking-algorithm](https://github.com/labuladong/fucking-algorithm)
- Tags: tutorial
- Published: 2026-02-25

---

**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:

```java
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:

```java
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:

```java
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:

```java
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):

```java
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):

```java
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)

```java
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)

```java
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

```java
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)

```java
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.