回溯算法秒杀所有排列-组合-子集问题

labuladong原创回溯算法约 12035 字

Info

已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	Difficulty
216. Combination Sum III	🟠
39. Combination Sum	🟠
40. Combination Sum II	🟠
46. Permutations	🟠
47. Permutations II	🟠
77. Combinations	🟠
78. Subsets	🟠
90. Subsets II	🟠

Prerequisites

Before reading this article, you should first learn:

Tip

本文有视频版：Solving All Permutation/Combination/Subset Problems with Backtracking。建议关注我的 B 站账号，我会用视频领读的方式带大家学习那些稍有难度的算法技巧。

Although permutation, combination, and subset problems are learned in high school, writing algorithms to solve them can be quite challenging and requires good computational thinking. This article will discuss the core ideas for programming solutions to these problems, so you can handle any variations with ease, adapting to changes effortlessly.

Whether it's permutation, combination, or subset problems, simply put, you are asked to select several elements from a sequence nums according to given rules. There are mainly three variations:

Form 1: Elements are unique and non-reusable, meaning each element in nums is unique and can be used at most once. This is the most basic form.

For example, in combination, if the input nums = [2,3,6,7], the combinations that sum to 7 should only be [7].

Form 2: Elements can be repeated but are non-reusable, meaning elements in nums can be duplicated, but each element can still be used at most once.

For example, in combination, if the input nums = [2,5,2,1,2], the combinations that sum to 7 should be two: [2,2,2,1] and [5,2].

Form 3: Elements are unique and reusable, meaning each element in nums is unique and can be used multiple times.

For example, in combination, if the input nums = [2,3,6,7], the combinations that sum to 7 should be two: [2,2,3] and [7].

Of course, there could be a fourth form where elements can be repeated and reusable. But if elements are reusable, why have duplicates? Removing duplicates would make it equivalent to Form 3, so this case doesn't need separate consideration.

The examples above use combination problems, but permutation, combination, and subset problems can all have these three basic forms, resulting in a total of 9 variations.

Additionally, problems can include various constraints. For example, finding combinations that sum to target with exactly k elements can lead to many variations. No wonder permutation and combination problems are frequently tested in interviews and exams.

Regardless of the form, the essence is to exhaust all solutions, which form a tree structure. By properly using the backtracking algorithm framework, you can solve these problems with slight modifications to the code.

Specifically, you need to first read and understand the previous article Core Backtracking Algorithm Techniques. Then, remember the backtracking trees for subset and permutation problems, which will help you solve all related permutation, combination, and subset problems:

Why can remembering these two tree structures solve all related problems?

Firstly, combination and subset problems are essentially equivalent, which will be explained later. The three variations mentioned earlier are simply about pruning or adding branches to these two trees.

Next, let's start exhausting all possibilities, covering the 9 forms of permutation/combination/subset problems, and learn how to solve them using the backtracking algorithm.

Tip

Also, some readers might have seen different code solutions for permutation/subset/combination problems compared to what I introduce in this article. This is because there are two perspectives for exhaustive enumeration in backtracking algorithms. I will explain these in detail in the later article Ball and Box Model: Two Perspectives of Backtracking Enumeration. For now, follow my approach to learn.

Subsets (Elements Are Unique and Non-repeating)

LeetCode problem #78 "Subsets" addresses this issue:

The problem provides you with an input array nums containing unique elements, where each element can be used at most once. Your task is to return all possible subsets of nums.

The function signature is as follows:

java 🟢

List<List<Integer>> subsets(int[] nums)

cpp 🤖

vector<vector<int>> subsets(vector<int>& nums)

python 🤖

def subsets(nums: List[int]) -> List[List[int]]:

go 🤖

func subsets(nums []int) [][]int

javascript 🤖

function subsets(nums) {}

For example, given the input nums = [1,2,3], the algorithm should return the following subsets:

[ [],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3] ]

Alright, let's not worry about the code implementation for now. Let's recall our high school knowledge: how do we manually derive all subsets?

First, generate the subset with 0 elements, which is the empty set []. For convenience, I'll call this S_0.

Next, based on S_0, generate all subsets with 1 element, which I'll call S_1:

Then, we can derive S_2 from S_1, which includes all subsets with 2 elements:

Why does the set [2] only need to add 3 and not the preceding 1?

Because the order of elements in a set doesn't matter. In [1,2,3], only 3 follows 2. If you add the preceding 1, the set [2,1] would be a duplicate of the already generated subset [1,2].

In other words, we prevent duplicate subsets by ensuring the relative order of elements remains unchanged.

Next, we can derive S_3 from S_2. In fact, S_3 contains only one set [1,2,3], which is derived from [1,2].

The entire derivation process forms this tree:

Notice the characteristics of this tree:

If we consider the root node as the 0th level and the elements on the branches between each node and the root as the node's value, then all nodes at level n are the subsets of size n.

For example, subsets of size 2 are the values of nodes at this level:

Combinations (Elements are Unique and Non-repetitive)

If you can successfully generate all unique subsets, you can easily modify your code to generate all unique combinations.

For example, if you are asked to form all combinations of 2 elements from nums = [1,2,3], how would you do it?

A little thought reveals that all combinations of size 2 are simply all subsets of size 2.

Therefore, I say that combinations and subsets are the same: a combination of size k is a subset of size k.

For instance, LeetCode problem #77 "Combinations":

Given two integers n and k, return all possible combinations of k numbers in the range [1, n].

The function signature is as follows:

java 🟢

List<List<Integer>> combine(int n, int k)

cpp 🤖

vector<vector<int>> combine(int n, int k)

python 🤖

def combine(n: int, k: int) -> List[List[int]]:

go 🤖

func combine(n int, k int) [][]int

javascript 🤖

var combine = function (n, k) {}

For example, the return value of combine(3, 2) should be:

[ [1,2],[1,3],[2,3] ]

This is a standard combination problem, but let me translate it for you, and it turns into a subset problem:

Given an array nums = [1,2,...,n] and a positive integer k, generate all subsets of size k.

Still using nums = [1,2,3] as an example, earlier you were asked to find all subsets, which means collecting the values of all nodes; now you only need to collect the nodes at the 2nd level (considering the root node as level 0), which are all combinations of size 2:

In terms of code, you only need to slightly modify the base case to control the algorithm to collect values from nodes at the kth level:

java 🟢

class Solution {

    List<List<Integer>> res = new LinkedList<>();
    // record the recursive path of backtracking algorithm
    LinkedList<Integer> track = new LinkedList<>();

    // main function
    public List<List<Integer>> combine(int n, int k) {
        backtrack(1, n, k);
        return res;
    }

    void backtrack(int start, int n, int k) {
        // base case
        if (k == track.size()) {
            // reached the k-th level, collect the current node's value
            res.add(new LinkedList<>(track));
            return;
        }
        
        // standard framework of backtracking algorithm
        for (int i = start; i <= n; i++) {
            // make a choice
            track.addLast(i);
            // control the traversal of branches through the start parameter to avoid duplicate subsets
            backtrack(i + 1, n, k);
            // undo the choice
            track.removeLast();
        }
    }
}

cpp 🤖

class Solution {
public:
    vector<vector<int>> res;
    // record the recursive path of backtracking algorithm
    deque<int> track;

    // main function
    vector<vector<int>> combine(int n, int k) {
        backtrack(1, n, k);
        return res;
    }

    void backtrack(int start, int n, int k) {
        // base case
        if (k == track.size()) {
            // reached the k-th level, collect the current node's value
            res.push_back(vector<int>(track.begin(), track.end()));
            return;
        }

        // standard framework of backtracking algorithm
        for (int i = start; i <= n; i++) {
            // make a choice
            track.push_back(i);
            // control the traversal of branches through the start parameter to avoid generating duplicate subsets
            backtrack(i + 1, n, k);
            // undo the choice
            track.pop_back();
        }
    }
};

python 🤖

class Solution:
    def __init__(self):
        self.res = []
        # record the recursive path of backtracking algorithm
        self.track = []

    # main function
    def combine(self, n: int, k: int) -> List[List[int]]:
        self.backtrack(1, n, k)
        return self.res

    def backtrack(self, start: int, n: int, k: int) -> None:
        # base case
        if k == len(self.track):
            # reached the k-th level, collect the current node's value
            self.res.append(self.track.copy())
            return
        
        # standard framework of backtracking algorithm
        for i in range(start, n+1):
            # make a choice
            self.track.append(i)
            # control the traversal of branches through the start parameter to avoid generating duplicate subsets
            self.backtrack(i + 1, n, k)
            # undo the choice
            self.track.pop()

go 🤖

func combine(n int, k int) [][]int {
    var res [][]int
    // record the recursive path of backtracking algorithm
    var track []int

    // the core function of backtracking algorithm
    var backtrack func(int)
    backtrack = func(start int) {
        // base case
        if k == len(track) {
            // reached the k-th level, collect the current node's value
            res = append(res, append([]int(nil), track...))
            return
        }

        // the standard framework of backtracking algorithm
        for i := start; i <= n; i++ {
            // make a choice
            track = append(track, i)
            // control the traversal of branches through the start parameter to avoid duplicate subsets
            backtrack(i + 1)
            // undo the choice
            track = track[:len(track)-1]
        }
    }

    backtrack(1)
    return res
}

javascript 🤖

var combine = function(n, k) {
    const res = [];
    // record the recursive path of the backtracking algorithm
    const track = [];

    // the core function of the backtracking algorithm
    const backtrack = (start) => {
        // base case
        if (k === track.length) {
            // reached the k-th level, collect the value of the current node
            res.push([...track]);
            return;
        }

        // the standard framework of the backtracking algorithm
        for (let i = start; i <= n; i++) {
            // make a choice
            track.push(i);
            // control the traversal of branches through the start parameter to avoid generating duplicate subsets
            backtrack(i + 1);
            // undo the choice
            track.pop();
        }
    };

    backtrack(1);
    return res;
};

With this, the standard combination problem is also solved.

Permutations (Elements are Unique and Non-repetitive)

The permutation problem was discussed in the previous article Backtracking Algorithm Core Framework. Here, we'll briefly review it.

LeetCode problem #46 "Permutations" is a standard permutation problem:

Given an array nums containing distinct integers, return all possible permutations of it.

The function signature is as follows:

java 🟢

List<List<Integer>> permute(int[] nums)

cpp 🤖

vector<vector<int>> permute(vector<int>& nums)

python 🤖

from typing import List

def permute(nums: List[int]) -> List[List[int]]:

go 🤖

func permute(nums []int) [][]int {}

javascript 🤖

var permute = function(nums) {}

比如输入 nums = [1,2,3]，函数的返回值应该是：

[
    [1,2,3],[1,3,2],
    [2,1,3],[2,3,1],
    [3,1,2],[3,2,1]
]

In the combination/subset problem we just discussed, the start variable ensures that only elements from nums[start+1..] appear after nums[start]. This maintains the relative positions of elements to avoid duplicate subsets.

However, in permutation problems, you need to explore all possible positions of elements. nums[i] can also be followed by elements to its left, so the previous approach doesn't work. We need to use an additional used array to mark which elements can still be chosen.

A standard full permutation can be abstracted into the following multi-branch tree:

We use the used array to mark elements already in the path to avoid duplicate selections. Then, we collect all values at the leaf nodes, which represent all possible full permutations:

java 🟢

class Solution {

    List<List<Integer>> res = new LinkedList<>();
    // record the recursive path of backtracking algorithm
    LinkedList<Integer> track = new LinkedList<>();
    // elements in track will be marked as true
    boolean[] used;

    // main function, input a set of non-repeating numbers, return all permutations
    public List<List<Integer>> permute(int[] nums) {
        used = new boolean[nums.length];
        backtrack(nums);
        return res;
    }

    // core function of backtracking algorithm
    void backtrack(int[] nums) {
        // base case, reach the leaf node
        if (track.size() == nums.length) {
            // collect the value at the leaf node
            res.add(new LinkedList(track));
            return;
        }

        // standard framework of backtracking algorithm
        for (int i = 0; i < nums.length; i++) {
            // elements already in track, cannot be selected repeatedly
            if (used[i]) {
                continue;
            }
            // make a choice
            used[i] = true;
            track.addLast(nums[i]);
            // enter the next level of backtracking tree
            backtrack(nums);
            // cancel the choice
            track.removeLast();
            used[i] = false;
        }
    }
}

cpp 🤖

class Solution {
public:
    // the list to store all permutation results
    vector<vector<int>> res;
    // record the recursive path of backtracking algorithm
    list<int> track;
    // elements in track will be marked as true
    vector<bool> used;

    // main function, input a set of non-repeating numbers, return all permutations
    vector<vector<int>> permute(vector<int>& nums) {
        used = vector<bool>(nums.size(), false);
        backtrack(nums);
        return res;
    }

    // core function of backtracking algorithm
    void backtrack(vector<int>& nums) {
        // base case, reach the leaf node
        if (track.size() == nums.size()) {
            // collect the value on the leaf node
            res.push_back(vector<int>(track.begin(), track.end()));
            return;
        }
        // standard framework of backtracking algorithm
        for (int i = 0; i < nums.size(); i++) {
            // elements already in track, cannot be selected again
            if (used[i]) {
                continue;
            }
            // make a choice
            used[i] = true;
            track.push_back(nums[i]);
            // go to the next level of backtracking tree
            backtrack(nums);
            // undo the choice
            track.pop_back();
            used[i] = false;
        }
    }
};

python 🤖

class Solution:
    def __init__(self):
        # a list to store all permutation results
        self.res = []
        # record the recursive path of backtracking algorithm
        self.track = []
        # elements in track will be marked as true
        self.used = []
    
    # main function, input a set of non-repeating numbers, return all permutations
    def permute(self, nums: List[int]) -> List[List[int]]:
        self.used = [False] * len(nums)
        self.backtrack(nums)
        return self.res
    
    # core function of backtracking algorithm
    def backtrack(self, nums: List[int]) -> None:
        # base case, reach the leaf node
        if len(self.track) == len(nums):
            # collect the value at the leaf node
            self.res.append(self.track[:])
            return
        
        # standard framework of backtracking algorithm
        for i in range(len(nums)):
            # elements already in track, cannot be selected repeatedly
            if self.used[i]:
                continue
            # make a choice
            self.used[i] = True
            self.track.append(nums[i])
            # enter the next level of backtracking tree
            self.backtrack(nums)
            # cancel the choice
            self.track.pop()
            self.used[i] = False

go 🤖

func permute(nums []int) [][]int {
    var res [][]int
    // record the recursive path of backtracking algorithm
    var track []int
    // elements in track will be marked as true
    used := make([]bool, len(nums))

    backtrack(nums, &res, track, used)

    return res
}

// core function of backtracking algorithm
func backtrack(nums []int, res *[][]int, track []int, used []bool) {
    // base case, reach the leaf node
    if len(track) == len(nums) {
        // collect the values at the leaf node
        tmp := make([]int, len(track))
        copy(tmp, track)
        *res = append(*res, tmp)
        return
    }

    // standard framework of backtracking algorithm
    for i := 0; i < len(nums); i++ {
        // elements already in track cannot be selected again
        if used[i] {
            continue
        }
        // make a choice
        used[i] = true
        track = append(track, nums[i])
        // enter the next level of backtracking tree
        backtrack(nums, res, track, used)
        // cancel the choice
        track = track[:len(track)-1]
        used[i] = false
    }
}

javascript 🤖

var permute = function(nums) {
    const res = [];
    // record the recursive path of backtracking algorithm
    const track = [];
    // elements in track will be marked as true
    const used = new Array(nums.length).fill(false);

    backtrack(nums, res, track, used);
    return res;
};

// core function of backtracking algorithm
function backtrack(nums, res, track, used) {
    // base case, reach the leaf node
    if (track.length === nums.length) {
        // collect the value at the leaf node
        res.push([...track]);
        return;
    }

    // standard framework of backtracking algorithm
    for (let i = 0; i < nums.length; i++) {
        // elements already in track cannot be selected again
        if (used[i]) {
            continue;
        }
        // make a choice
        used[i] = true;
        track.push(nums[i]);
        // go to the next level of backtracking tree
        backtrack(nums, res, track, used);
        // undo the choice
        track.pop();
        used[i] = false;
    }
}

This way, the permutation problem is solved.

But what if the problem asks you to find permutations with exactly k elements, instead of all permutations?

It's also simple. Just modify the base case of the backtrack function to collect only the node values at the k-th level:

java 🟢

// core function of backtracking algorithm
void backtrack(int[] nums, int k) {
    // base case, reach the k-th level, collect the value of the node
    if (track.size() == k) {
        // the value of the k-th level node is a permutation of size k
        res.add(new LinkedList(track));
        return;
    }

    // standard framework of backtracking algorithm
    for (int i = 0; i < nums.length; i++) {
        // ...
        backtrack(nums, k);
        // ...
    }
}

cpp 🤖

// backtracking core function
void backtrack(vector<int>& nums, int k) {
    // base case, reach the k-th level, collect the node's value
    if (track.size() == k) {
        // the value of the k-th level node is the permutation of size k
        res.push_back(track);
        return;
    }

    // standard framework of backtracking algorithm
    for (int i = 0; i < nums.size(); i++) {
        // ...
        backtrack(nums, k, res, track);
        // ...
    }
}

python 🤖

# Core function of backtracking algorithm
def backtrack(nums: List[int], k: int) -> None:
    # base case, reach the k-th level, collect the value of the node
    if len(track) == k:
        # the value of the k-th level node is the permutation of size k
        res.append(track[:])
        return

    # Standard framework of backtracking algorithm
    for i in range(len(nums)):
        # ...
        backtrack(nums, k)
        # ...

go 🤖

func backtrack(nums []int, k int) {
    // base case, reach the k-th level, collect the node's value
    if len(track) == k {
        // the value of the k-th level node is the permutation of size k
        res = append(res, append([]int(nil), track...))
        return
    }

    // backtracking algorithm standard framework
    for i := 0; i < len(nums); i++ {
        // ...
        backtrack(nums, k)
        // ...
    }
}

javascript 🤖

// core function of backtracking algorithm
var backtrack = function(nums, k) {
    // base case, reach the k-th level, collect the values of the nodes
    if (track.size() == k) {
        // the values at the k-th level are the permutations of size k
        res.add(new LinkedList(track));
        return;
    }

    // standard framework of backtracking algorithm
    for (var i = 0; i < nums.length; i++) {
        // ...
        backtrack(nums, k);
        // ...
    }
};

Subsets/Combinations (Elements Can Repeat but Not Re-selectable)

We just discussed the standard subset problem where the input nums has no duplicate elements. But how do we handle it if there are duplicates?

LeetCode Problem 90, "Subsets II," is exactly this kind of problem:

Given an integer array nums that may contain duplicates, return all possible subsets of the array.

The function signature is as follows:

java 🟢

List<List<Integer>> subsetsWithDup(int[] nums)

cpp 🤖

vector<vector<int>> subsetsWithDup(vector<int>& nums)

python 🤖

def subsetsWithDup(nums: List[int]) -> List[List[int]]:

go 🤖

func subsetsWithDup(nums []int) [][]int

javascript 🤖

var subsetsWithDup = function(nums) {}

For example, given the input nums = [1,2,2], you should output:

[ [], [1], [2], [1,2], [2,2], [1,2,2] ]

Technically, a "set" should not contain duplicate elements, but since the problem asks for it, let's ignore this detail and focus on how to solve the problem.

Taking nums = [1,2,2] as an example, to distinguish between the two different 2s, we'll write it as nums = [1,2,2'].

Following the previous approach to draw the tree structure of subsets, it's clear that adjacent branches with the same value will produce duplicates:

[
    [],
    [1], [2], [2'],
    [1,2], [1,2'], [2,2'],
    [1,2,2']
]

You can see that the results [2] and [1,2] are duplicated. Therefore, we need to prune the tree. If a node has multiple adjacent branches with the same value, we only traverse the first one and skip the rest:

In the code, this means we need to sort the array first to group identical elements together. If we find nums[i] == nums[i-1], we skip it:

java 🟢

class Solution {

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

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // sort first, let the same elements be together
        Arrays.sort(nums);
        backtrack(nums, 0);
        return res;
    }

    void backtrack(int[] nums, int start) {
        // preorder position, the value of each node is a subset
        res.add(new LinkedList<>(track));
        
        for (int i = start; i < nums.length; i++) {
            // pruning logic, only traverse the first branch of adjacent branches with the same value
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            track.addLast(nums[i]);
            backtrack(nums, i + 1);
            track.removeLast();
        }
    }
}

cpp 🤖

class Solution {
public:
    vector<vector<int>> res;
    deque<int> track;

    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        // sort first to make the same elements adjacent
        sort(nums.begin(), nums.end());
        backtrack(nums, 0);
        return res;
    }

    void backtrack(vector<int>& nums, int start) {
        // in the preorder position, the value of each node is a subset
        res.push_back(vector<int>(track.begin(), track.end()));
        
        for (int i = start; i < nums.size(); i++) {
            // pruning logic, only traverse the first branch for adjacent branches with the same value
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            track.push_back(nums[i]);
            backtrack(nums, i + 1);
            track.pop_back();
        }
    }
};

python 🤖

class Solution:
    def __init__(self):
        self.res = []
        self.track = []
    
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        # sort first to make the same elements adjacent
        nums.sort()
        self.backtrack(nums, 0)
        return self.res
    
    def backtrack(self, nums: List[int], start: int) -> None:
        # in the pre-order position, the value of each node is a subset
        self.res.append(self.track[:])
        
        for i in range(start, len(nums)):
            # pruning logic, only traverse the first branch for adjacent branches with the same value
            if i > start and nums[i] == nums[i - 1]:
                continue
            self.track.append(nums[i])
            self.backtrack(nums, i + 1)
            self.track.pop()

go 🤖

func subsetsWithDup(nums []int) [][]int {
    var res [][]int
    var track []int
    
    // sort first, let the same elements be together
    sort.Ints(nums)
    backtrack(nums, &track, &res, 0)
    
    return res
}

func backtrack(nums []int, track *[]int, res *[][]int, start int) {
    // in the preorder position, the value of each node is a subset
    tmp := make([]int, len(*track))
    copy(tmp, *track)
    *res = append(*res, tmp)
    
    for i := start; i < len(nums); i++ {
        // pruning logic, only traverse the first branch for adjacent branches with the same value
        if i > start && nums[i] == nums[i-1] {
            continue
        }
        *track = append(*track, nums[i])
        backtrack(nums, track, res, i+1)
        *track = (*track)[:len(*track)-1]
    }
}

javascript 🤖

var subsetsWithDup = function(nums) {
    let res = [];
    let track = [];

    // sort first, let the same elements be together
    nums.sort((a, b) => a - b);
    backtrack(nums, track, res, 0);

    return res;
};

var backtrack = function(nums, track, res, start) {
    // the position before recursion, the value of each node is a subset
    res.push([...track]);

    for (let i = start; i < nums.length; i++) {
        // pruning logic, only traverse the first branch for adjacent branches with the same value
        if (i > start && nums[i] === nums[i - 1]) {
            continue;
        }
        track.push(nums[i]);
        backtrack(nums, track, res, i + 1);
        track.pop();
    }
};

This code is almost identical to the standard subset problem code, with the addition of sorting and pruning logic.

As for why we prune this way, it should be easy to understand when combined with the previous diagram. This approach also solves the subset problem with duplicate elements.

We mentioned that the combination problem and the subset problem are equivalent, so let's directly look at a combination problem. This is LeetCode problem #40, "Combination Sum II":

You are given an input candidates and a target sum target. Find all unique combinations in candidates where the numbers sum to target.

candidates may contain duplicates, and each number can be used at most once.

Although this is framed as a combination problem, it can be rephrased as a subset problem: Calculate all subsets of candidates that sum to target.

So, how do we solve this problem?

By comparing the solution to the subset problem, we just need to add an extra trackSum variable to keep track of the sum of elements in the backtrack path, and then modify the base case accordingly to solve this problem:

java 🟢

class Solution {

    List<List<Integer>> res = new LinkedList<>();
    // record the backtracking path
    LinkedList<Integer> track = new LinkedList<>();
    // record the sum of elements in track
    int trackSum = 0;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if (candidates.length == 0) {
            return res;
        }
        // sort first, let the same elements be together
        Arrays.sort(candidates);
        backtrack(candidates, 0, target);
        return res;
    }

    // main function of backtracking algorithm
    void backtrack(int[] nums, int start, int target) {
        // base case, reach the target sum, find a qualified combination
        if (trackSum == target) {
            res.add(new LinkedList<>(track));
            return;
        }
        // base case, exceed the target sum, end directly
        if (trackSum > target) {
            return;
        }

        // standard framework of backtracking algorithm
        for (int i = start; i < nums.length; i++) {
            // pruning logic, only traverse the first branch with the same value
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            // make a choice
            track.add(nums[i]);
            trackSum += nums[i];
            // recursively traverse the next level of backtracking tree
            backtrack(nums, i + 1, target);
            // cancel the choice
            track.removeLast();
            trackSum -= nums[i];
        }
    }
}

cpp 🤖

class Solution {
public:
    vector<vector<int>> res;
    // record the backtracking path
    vector<int> track;
    // record the sum of elements in track
    int trackSum = 0;

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        // sort first to let the same elements be together
        sort(candidates.begin(), candidates.end());
        backtrack(candidates, 0, target);
        return res;
    }

    // main function of backtracking algorithm
    void backtrack(vector<int>& nums, int start, int target) {
        // base case, reach the target sum, find a valid combination
        if(trackSum == target) {
            res.push_back(track);
            return;
        }
        // base case, exceed the target sum, end directly
        if(trackSum > target) {
            return;
        }

        // standard framework of backtracking algorithm
        for(int i = start; i < nums.size(); i++) {
            // pruning logic, only traverse the first branch with the same value
            if(i > start && nums[i] == nums[i-1]) {
                continue;
            }
            // make a choice
            track.push_back(nums[i]);
            trackSum += nums[i];
            // recursively traverse the next level of backtracking tree
            backtrack(nums, i+1, target);
            // undo the choice
            track.pop_back();
            trackSum -= nums[i];
        }
    }
};

python 🤖

class Solution:
    def __init__(self):
        self.res = []
        # record the backtracking path
        self.track = []
        # record the sum of elements in track
        self.trackSum = 0
    
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        if not candidates:
            return self.res
        # sort first, let the same elements be together
        candidates.sort()
        self.backtrack(candidates, 0, target)
        return self.res
    
    # main function of backtracking algorithm
    def backtrack(self, nums: List[int], start: int, target: int):
        # base case, reach the target sum, find a valid combination
        if self.trackSum == target:
            self.res.append(self.track[:])
            return
        # base case, exceed the target sum, end directly
        if self.trackSum > target:
            return
        
        # standard framework of backtracking algorithm
        for i in range(start, len(nums)):
            # pruning logic, only traverse the first branch with the same value
            if i > start and nums[i] == nums[i - 1]:
                continue
            # make a choice
            self.track.append(nums[i])
            self.trackSum += nums[i]
            # recursively traverse the next level of backtracking tree
            self.backtrack(nums, i + 1, target)
            # cancel the choice
            self.track.pop()
            self.trackSum -= nums[i]

go 🤖

func combinationSum2(candidates []int, target int) [][]int {
    var res [][]int
    var track []int
    // record the sum of elements in track
    var trackSum int

    // sort first, so that the same elements are together
    sort.Ints(candidates)
    backtrack(candidates, target, 0, &track, &res, &trackSum)

    return res
}

// main function of backtracking algorithm
func backtrack(nums []int, target, start int, track *[]int, res *[][]int, trackSum *int) {
    // base case, reach the target sum, find a qualified combination
    if *trackSum == target {
        tmp := make([]int, len(*track))
        copy(tmp, *track)
        *res = append(*res, tmp)
        return
    }
    // base case, exceed the target sum, end directly
    if *trackSum > target {
        return
    }

    // standard framework of backtracking algorithm
    for i := start; i < len(nums); i++ {
        // pruning logic, only traverse the first branch with the same value
        if i > start && nums[i] == nums[i-1] {
            continue
        }
        // make a choice
        *track = append(*track, nums[i])
        *trackSum += nums[i]
        // recursively traverse the next level of backtracking tree
        backtrack(nums, target, i+1, track, res, trackSum)
        // undo the choice
        *track = (*track)[:len(*track)-1]
        *trackSum -= nums[i]
    }
}

javascript 🤖

var combinationSum2 = function(candidates, target) {
    let res = [];
    // record the backtracking path
    let track = [];
    // record the sum of elements in track
    let trackSum = 0;

    // sort first, to make the same elements adjacent
    candidates.sort((a, b) => a - b);
    
    var backtrack = function(nums, target, start) {
        // base case, reach the target sum, find a valid combination
        if (trackSum === target) {
            res.push([...track]);
            return;
        }
        // base case, exceed the target sum, end directly
        if (trackSum > target) {
            return;
        }

        // standard framework of backtracking algorithm
        for (let i = start; i < nums.length; i++) {
            // pruning logic, only traverse the first branch with the same value
            if (i > start && nums[i] === nums[i - 1]) {
                continue;
            }
            // make a choice
            track.push(nums[i]);
            trackSum += nums[i];
            // recursively traverse the next level of backtracking tree
            backtrack(nums, target, i + 1);
            // undo the choice
            track.pop();
            trackSum -= nums[i];
        }
    };

    backtrack(candidates, target, 0);

    return res;
};

Permutations (Elements Can Repeat, No Repetition Allowed)

When dealing with permutation problems where the input contains duplicates, it is slightly more complex than subset/combination problems. Let's look at LeetCode problem #47 "Permutations II":

Given a sequence nums that may contain duplicate numbers, write an algorithm to return all possible permutations. The function signature is as follows:

java 🟢

List<List<Integer>> permuteUnique(int[] nums)

cpp 🤖

vector<vector<int>> permuteUnique(vector<int>& nums)

python 🤖

def permuteUnique(nums: List[int]) -> List[List[int]]:

go 🤖

func permuteUnique(nums []int) [][]int

javascript 🤖

var permuteUnique = function(nums) {}

For example, if the input is nums = [1,2,2], the function returns:

[ [1,2,2],[2,1,2],[2,2,1] ]

Let's look at the solution code:

java 🟢

class Solution {

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

    public List<List<Integer>> permuteUnique(int[] nums) {
        // sort first, let the same elements be together
        Arrays.sort(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;
            }
            // newly added pruning logic, fix the relative positions of the same elements in the permutation
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }
            track.add(nums[i]);
            used[i] = true;
            backtrack(nums);
            track.removeLast();
            used[i] = false;
        }
    }
}

cpp 🤖

class Solution {
public:
    vector<vector<int>> res;
    vector<int> track;
    vector<bool> used;

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        // sort first to make the same elements adjacent
        sort(nums.begin(), nums.end());
        used = vector<bool>(nums.size(), false);
        backtrack(nums);
        return res;
    }

    void backtrack(vector<int>& nums) {
        if (track.size() == nums.size()) {
            res.push_back(track);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            if (used[i]) {
                continue;
            }
            // newly added pruning logic to fix the relative position of the same elements in the permutation
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }
            track.push_back(nums[i]);
            used[i] = true;
            backtrack(nums);
            track.pop_back();
            used[i] = false;
        }
    }
};

python 🤖

class Solution:
    def __init__(self):
        self.res = []
        self.track = []
        self.used = []
    
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        # sort first, let the same elements be together
        nums.sort()
        self.used = [False] * len(nums)
        self.backtrack(nums)
        return self.res
    
    def backtrack(self, nums: List[int]) -> None:
        if len(self.track) == len(nums):
            self.res.append(self.track[:])
            return

        for i in range(len(nums)):
            if self.used[i]:
                continue
            # newly added pruning logic, fix the relative position of the same elements in the permutation
            if i > 0 and nums[i] == nums[i - 1] and not self.used[i - 1]:
                continue
            self.track.append(nums[i])
            self.used[i] = True
            self.backtrack(nums)
            self.track.pop()
            self.used[i] = False

go 🤖

func permuteUnique(nums []int) [][]int {
    var res [][]int
    var track []int
    used := make([]bool, len(nums))

    // sort first, let the same elements be together
    sort.Ints(nums)
    backtrack(nums, &res, track, used)
    return res
}

func backtrack(nums []int, res *[][]int, track []int, used []bool) {
    if len(track) == len(nums) {
        tmp := make([]int, len(track))
        copy(tmp, track)
        *res = append(*res, tmp)
        return
    }

    for i := 0; i < len(nums); i++ {
        if used[i] {
            continue
        }
        // newly added pruning logic, fix the relative positions of the same elements in the permutation
        if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
            continue
        }
        track = append(track, nums[i])
        used[i] = true
        backtrack(nums, res, track, used)
        track = track[:len(track)-1]
        used[i] = false
    }
}

javascript 🤖

var permuteUnique = function(nums) {
    let res = [];
    let track = [];
    let used = new Array(nums.length).fill(false);

    // sort first, let the same elements be together
    nums.sort((a, b) => a - b);
    backtrack(nums, used, track, res);

    return res;
};

function backtrack(nums, used, track, res) {
    if (track.length === nums.length) {
        res.push(track.slice());
        return;
    }

    for (let i = 0; i < nums.length; i++) {
        if (used[i]) {
            continue;
        }
        // newly added pruning logic, fix the relative position of the same elements in the permutation
        if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) {
            continue;
        }
        track.push(nums[i]);
        used[i] = true;
        backtrack(nums, used, track, res);
        track.pop();
        used[i] = false;
    }
}

Compare this solution code with the previous standard full permutation solution code. There are only two differences in this solution:

The nums array is sorted.
An additional pruning logic is added.

Analogous to the subset/combination problems with duplicate elements, you should understand that this is done to prevent duplicate results.

However, note that the pruning logic for permutation problems is slightly different from that for subset/combination problems: it includes an additional logical check !used[i - 1].

Understanding this part requires some技巧. Let me explain it slowly. For ease of study, we still use superscripts ' to distinguish identical elements.

Assume the input is nums = [1,2,2']. The standard full permutation algorithm will produce the following results:

[
    [1,2,2'],[1,2',2],
    [2,1,2'],[2,2',1],
    [2',1,2],[2',2,1]
]

Clearly, there are duplicates in this result. For example, [1,2,2'] and [1,2',2] should be considered the same permutation, but they are counted as two different permutations.

So, the key now is how to design a pruning logic to remove these duplicates?

The answer is to ensure that the relative positions of identical elements in the permutation remain unchanged.

For instance, in the example nums = [1,2,2'], I keep the 2 always before 2' in the permutation.

This way, from the 6 permutations mentioned earlier, you can only pick 3 that meet this condition:

[ [1,2,2'], [2,1,2'], [2,2',1] ]

This is the correct answer.

Further, if nums = [1,2,2',2''], I just need to ensure the relative positions of the duplicate element 2 are fixed, such as 2 -> 2' -> 2'', to get a permutation result without duplicates.

Upon careful thought, it should be easy to understand the principle:

The standard permutation algorithm produces duplicates because it treats sequences formed by identical elements as different, but they should actually be the same; if we fix the order of sequences formed by identical elements, we naturally avoid duplicates.

Reflecting this in the code, pay attention to this pruning logic:

// Newly added pruning logic, fixing the relative position of the same elements in the permutation
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
    // If the previous adjacent equal element has not been used, skip it
    continue;
}
// Choose nums[i]

When there are duplicate elements, such as the input nums = [1,2,2',2''], 2' will only be chosen if 2 has already been used. Similarly, 2'' will only be chosen if 2' has already been used. This ensures that the relative positions of identical elements in the permutation remain fixed.

Let's expand on this. If you change !used[i - 1] to used[i - 1] in the above pruning logic, it can still pass all test cases, but the efficiency will decrease. Why is this?

The reason this modification doesn't produce errors is that it maintains the relative order of 2'' -> 2' -> 2, ultimately achieving the effect of deduplication.

But why does this approach reduce efficiency? Because it doesn't prune enough branches.

For example, with the input nums = [2,2',2''], the generated backtracking tree looks like this:

If green branches represent the paths traversed by the backtrack function and red branches represent the triggering of the pruning logic, then the backtracking tree obtained with the !used[i - 1] pruning logic looks like this:

While the backtracking tree obtained with the used[i - 1] pruning logic looks like this:

As you can see, the !used[i - 1] pruning logic prunes cleanly and efficiently, whereas the used[i - 1] pruning logic, although it also produces unique results, prunes fewer branches and involves more unnecessary calculations, hence the lower efficiency.

You can use the "Edit" button on the visualization panel to modify the code yourself and see the difference in the backtracking trees produced by the two approaches:

Of course, some readers have proposed other pruning strategies for permutation deduplication:

java 🟢

void backtrack(int[] nums, LinkedList<Integer> track) {
    if (track.size() == nums.length) {
        res.add(new LinkedList(track));
        return;
    }

    // record the value of the previous branch element
    // the problem statement says -10 <= nums[i] <= 10, so initialize to a special value
    int prevNum = -666;
    for (int i = 0; i < nums.length; i++) {
        // exclude illegal choices
        if (used[i]) {
            continue;
        }
        if (nums[i] == prevNum) {
            continue;
        }

        track.add(nums[i]);
        used[i] = true;
        // record the value on this branch
        prevNum = nums[i];

        backtrack(nums, track);

        track.removeLast();
        used[i] = false;
    }
}

cpp 🤖

void backtrack(vector<int>& nums, list<int>& track) {
    if (track.size() == nums.size()) {
        res.push_back(vector<int>(track.begin(), track.end()));
        return;
    }

    // record the value of the previous branch element
    // the problem states that -10 <= nums[i] <= 10, so initialize to a special value
    int prevNum = -666;
    for (int i = 0; i < nums.size(); i++) {
        // exclude invalid choices
        if (used[i]) {
            continue;
        }
        if (nums[i] == prevNum) {
            continue;
        }

        track.push_back(nums[i]);
        used[i] = true;
        // record the value on this branch
        prevNum = nums[i];

        backtrack(nums, track);

        track.pop_back();
        used[i] = false;
    }
}

python 🤖

def backtrack(nums: List[int], track: LinkedList[int]):
    if len(track) == len(nums):
        res.append(track[:])
        return

    # record the value of the element on the previous branch
    # the problem states that -10 <= nums[i] <= 10, so initialize to a special value
    prevNum = -666
    for i in range(len(nums)):
        # exclude illegal choices
        if used[i]:
            continue
        if nums[i] == prevNum:
            continue

        track.append(nums[i])
        used[i] = True
        # record the value on this branch
        prevNum = nums[i]

        backtrack(nums, track)

        track.pop()
        used[i] = False

go 🤖

func backtrack(nums []int, track []int) {
    if len(track) == len(nums) {
        tmp := make([]int, len(track))
        copy(tmp, track)
        res = append(res, tmp)
        return
    }

    // record the value of the element on the previous branch
    // the problem statement says -10 <= nums[i] <= 10, so initialize to a special value
    prevNum := -666
    for i := 0; i < len(nums); i++ {
        // exclude illegal choices
        if used[i] {
            continue
        }
        if nums[i] == prevNum {
            continue
        }

        track = append(track, nums[i])
        used[i] = true
        // record the value on this branch
        prevNum = nums[i]

        backtrack(nums, track)

        track = track[:len(track)-1]
        used[i] = false
    }
}

javascript 🤖

var backtrack = function(nums, track) {
    if (track.length === nums.length) {
        res.push([...track]);
        return;
    }

    // record the value of the element on the previous branch
    // the problem states that -10 <= nums[i] <= 10, so initialize to a special value
    let prevNum = -666;
    for (let i = 0; i < nums.length; i++) {
        // exclude illegal choices
        if (used[i]) {
            continue;
        }
        if (nums[i] === prevNum) {
            continue;
        }

        track.push(nums[i]);
        used[i] = true;
        // record the value on this branch
        prevNum = nums[i];

        backtrack(nums, track);

        track.pop();
        used[i] = false;
    }
};

This approach is also correct. Imagine a scenario where a node has identical branches:

If left untreated, the subtrees beneath these identical branches will also grow identically, resulting in duplicate permutations.

Since all equal elements are adjacent after sorting, you can avoid traversing branches with the same value by recording the value of the previous branch with prevNum. This prevents the creation of identical subtrees and ultimately avoids duplicate permutations.

Great, now we've also solved the permutation problem with duplicate inputs.

Subsets/Combinations (Elements are Unique and Can Be Repeated)

Finally, we've reached the last type: the input array has no duplicate elements, but each element can be used an unlimited number of times.

Let's directly look at LeetCode problem 39, "Combination Sum":

Given an array of distinct integers candidates and a target integer target, find all combinations in candidates that can add up to the target target. Each number in candidates can be used multiple times without any restriction.

The function signature is as follows:

java 🟢

List<List<Integer>> combinationSum(int[] candidates, int target)

cpp 🤖

vector<vector<int>> combinationSum(vector<int>& candidates, int target)

python 🤖

def combinationSum(candidates: List[int], target: int) -> List[List[int]]:

go 🤖

func combinationSum(candidates []int, target int) [][]int

javascript 🤖

var combinationSum = function(candidates, target) {}

For example, given candidates = [1,2,3] and target = 3, the algorithm should return:

[ [1,1,1],[1,2],[3] ]

This problem is essentially about subsets: which subsets of candidates sum up to target?

To solve this type of problem, we need to go back to the backtracking tree. Let's think about how standard subset/combination problems ensure that elements are not reused.

The answer lies in the start parameter passed to the backtrack recursive function:

java 🟢

// Backtracking algorithm framework without repetition
void backtrack(int[] nums, int start) {
    for (int i = start; i < nums.length; i++) {
        // ...
        // Recursively traverse the next level of the backtracking tree, pay attention to the parameters
        backtrack(nums, i + 1);
        // ...
    }
}

cpp 🤖

// Backtracking algorithm framework for non-repeating combinations
void backtrack(vector<int>& nums, int start) {
    for (int i = start; i < nums.size(); i++) {
        // ...
        // Recursively traverse the next level of the backtracking tree, note the parameters
        backtrack(nums, i + 1);
        // ...
    }
}

python 🤖

# Backtracking algorithm framework without repetition
def backtrack(nums: List[int], start: int) -> None:
    for i in range(start, len(nums)):
        # ...
        # Recursively traverse the next level of the backtracking tree, pay attention to the parameters
        backtrack(nums, i + 1)
        # ...

go 🤖

// Backtracking algorithm framework without repetition
func backtrack(nums []int, start int) {
    for i := start; i < len(nums); i++ {
        // ...
        // Recursively traverse the next level of the backtracking tree, note the parameters
        backtrack(nums, i + 1)
        // ...
    }
}

javascript 🤖

// Framework of backtracking algorithm without repetition
var backtrack = function(nums, start) {
    for (var i = start; i < nums.length; i++) {
        // ...
        // Recursively traverse the next level of the backtracking tree, note the parameters
        backtrack(nums, i + 1);
        // ...
    }
};

This i starts from start, so in the next level of the backtracking tree, it starts from start + 1, ensuring that the element nums[start] is not reused:

Conversely, if I want each element to be reusable, I just need to change i + 1 to i:

java 🟢

// Backtracking algorithm framework with reusable combinations
void backtrack(int[] nums, int start) {
    for (int i = start; i < nums.length; i++) {
        // ...
        // Recursively traverse the next level of backtracking tree, note the parameters
        backtrack(nums, i);
        // ...
    }
}

cpp 🤖

// Framework of backtracking algorithm with reusable combinations
void backtrack(vector<int>& nums, int start) {
    for (int i = start; i < nums.size(); i++) {
        // ...
        // Recursively traverse the next level of backtracking tree, note the parameters
        backtrack(nums, i);
        // ...
    }
}

python 🤖

# Backtracking algorithm framework with reusable combinations
def backtrack(nums: List[int], start: int):
    for i in range(start, len(nums)):
        # ...
        # Recursively traverse the next level of the backtracking tree, note the parameters
        backtrack(nums, i)
        # ...

go 🤖

// Frame of backtracking algorithm with reusable combinations
func backtrack(nums []int, start int) {
    for i := start; i < len(nums); i++ {
        // ...
        // Recursively traverse the next level of the backtracking tree, note the parameters
        backtrack(nums, i)
        // ...
    }
}

javascript 🤖

// Frame of backtracking algorithm with reusable combinations
var backtrack = function(nums, start) {
    for (var i = start; i < nums.length; i++) {
        // ...
        // Recursively traverse the next level of the backtracking tree, note the parameters
        backtrack(nums, i);
        // ...
    }
};

This is equivalent to adding a branch to the previous backtracking tree. During the traversal of this tree, an element can be used an unlimited number of times:

Of course, this way the backtracking tree will keep growing indefinitely. Therefore, our recursive function needs to set an appropriate base case to terminate the algorithm, which means there's no need to continue traversing when the path sum exceeds the target.

The solution code for this problem is as follows:

java 🟢

class Solution {

    List<List<Integer>> res = new LinkedList<>();
    // record the backtracking path
    LinkedList<Integer> track = new LinkedList<>();
    // record the sum of the path in track
    int trackSum = 0;

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

    // main function of backtracking algorithm
    void backtrack(int[] nums, int start, int target) {
        // base case, find the target sum, record the result
        if (trackSum == target) {
            res.add(new LinkedList<>(track));
            return;
        }
        // base case, exceed the target sum, stop traversing downwards
        if (trackSum > target) {
            return;
        }
        // standard framework of backtracking algorithm
        for (int i = start; i < nums.length; i++) {
            // choose nums[i]
            trackSum += nums[i];
            track.add(nums[i]);
            // recursively traverse the next level of backtracking tree
            backtrack(nums, i, target);
            // the same element can be used repeatedly, note the parameter
            // undo the choice of nums[i]
            trackSum -= nums[i];
            track.removeLast();
        }
    }
}

cpp 🤖

class Solution {
public:
    vector<vector<int>> res;
    // record the backtracking path
    deque<int> track;
    // record the sum of the path in track
    int trackSum = 0;

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        backtrack(candidates, 0, target);
        return res;
    }

    // main function of backtracking algorithm
    void backtrack(vector<int>& nums, int start, int target) {
        // base case, find the target sum, record the result
        if (trackSum == target) {
            res.push_back(vector<int>(track.begin(), track.end()));
            return;
        }
        // base case, exceed the target sum, stop traversing downwards
        if (trackSum > target) {
            return;
        }
        // standard framework of backtracking algorithm
        for (int i = start; i < nums.size(); i++) {
            // choose nums[i]
            trackSum += nums[i];
            track.push_back(nums[i]);
            // recursively traverse the next level of the backtracking tree
            // the same element can be used repeatedly, note the parameter
            backtrack(nums, i, target);
            // undo the choice of nums[i]
            trackSum -= nums[i];
            track.pop_back();
        }
    }
};

python 🤖

class Solution:
    def __init__(self):
        self.res = []
        # record the backtracking path
        self.track = []
        # record the sum of the path in track
        self.trackSum = 0

    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        if len(candidates) == 0:
            return self.res
        self.backtrack(candidates, 0, target)
        return self.res

    # main function of backtracking algorithm
    def backtrack(self, nums: List[int], start: int, target: int) -> None:
        # base case, find the target sum, record the result
        if self.trackSum == target:
            self.res.append(list(self.track))
            return
        # base case, exceed the target sum, stop traversing down
        if self.trackSum > target:
            return

        # standard framework of backtracking algorithm
        for i in range(start, len(nums)):
            # choose nums[i]
            self.trackSum += nums[i]
            self.track.append(nums[i])
            # recursively traverse the next level of the backtracking tree
            # the same element can be used repeatedly, pay attention to the parameters
            self.backtrack(nums, i, target)
            # undo the choice of nums[i]
            self.trackSum -= nums[i]
            self.track.pop()

go 🤖

func combinationSum(candidates []int, target int) [][]int {
    var res [][]int
    // record the backtracking path
    var track []int
    // record the sum of the path in track
    trackSum := 0

    var backtrack func([]int, int)
    backtrack = func(nums []int, start int) {
        // base case, find the target sum, record the result
        if trackSum == target {
            tmp := make([]int, len(track))
            copy(tmp, track)
            res = append(res, tmp)
            return
        }
        // base case, exceed the target sum, stop traversing down
        if trackSum > target {
            return
        }
        // standard framework for backtracking algorithm
        for i := start; i < len(nums); i++ {
            // choose nums[i]
            trackSum += nums[i]
            track = append(track, nums[i])
            // recursively traverse the next level of the backtracking tree
            // the same element can be used repeatedly, note the parameter
            backtrack(nums, i)
            // undo the choice of nums[i]
            trackSum -= nums[i]
            track = track[:len(track)-1]
        }
    }

    backtrack(candidates, 0)
    return res
}

javascript 🤖

var combinationSum = function (candidates, target) {
    // record the result
    var res = [];
    // record the backtracking path
    var track = [];
    // record the sum of the path in track
    var trackSum = 0;

    // main function of backtracking algorithm
    function backtrack(nums, start) {
        // base case, find the target sum, record the result
        if (trackSum === target) {
            res.push([...track]);
            return;
        }
        // base case, exceed the target sum, stop traversing downwards
        if (trackSum > target) {
            return;
        }

        // standard framework of backtracking algorithm
        for (var i = start; i < nums.length; i++) {
            // choose nums[i]
            trackSum += nums[i];
            track.push(nums[i]);
            // recursively traverse the next level of backtracking tree
            // the same element can be used repeatedly, note the parameter
            backtrack(nums, i);
            // undo the choice of nums[i]
            trackSum -= nums[i];
            track.pop();
        }
    }

    backtrack(candidates, 0);
    return res;
};

Permutations (Elements are Unique and Can Be Repeated)

There are no direct problems on LeetCode that test this scenario. Let's think about it: if the elements in the nums array are unique and can be repeated, what permutations are possible?

For example, if the input is nums = [1,2,3], then under these conditions, there are a total of 3^3 = 27 permutations:

[
  [1,1,1],[1,1,2],[1,1,3],[1,2,1],[1,2,2],[1,2,3],[1,3,1],[1,3,2],[1,3,3],
  [2,1,1],[2,1,2],[2,1,3],[2,2,1],[2,2,2],[2,2,3],[2,3,1],[2,3,2],[2,3,3],
  [3,1,1],[3,1,2],[3,1,3],[3,2,1],[3,2,2],[3,2,3],[3,3,1],[3,3,2],[3,3,3]
]

The standard permutation algorithm uses a used array to prune branches and avoid reusing the same element. If elements can be reused, you can simply remove all the pruning logic related to the used array.

This makes the problem straightforward. Here is the code:

java 🟢

class Solution {

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

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

    // core function of backtracking algorithm
    void backtrack(int[] nums) {
        // base case, reaching the leaf node
        if (track.size() == nums.length) {
            // collect the values at the leaf node
            res.add(new LinkedList(track));
            return;
        }

        // standard framework of backtracking algorithm
        for (int i = 0; i < nums.length; i++) {
            // make a choice
            track.add(nums[i]);
            // enter the next level of backtracking tree
            backtrack(nums);
            // undo the choice
            track.removeLast();
        }
    }
}

cpp 🤖

class Solution {
public:
    vector<vector<int>> res;
    deque<int> track;

    vector<vector<int>> permuteRepeat(vector<int>& nums) {
        backtrack(nums);
        return res;
    }

    // backtracking core function
    void backtrack(vector<int>& nums) {
        // base case, reach the leaf node
        if (track.size() == nums.size()) {
            // collect the values at the leaf node
            res.push_back(vector<int>(track.begin(), track.end()));
            return;
        }

        // standard framework of backtracking algorithm
        for (int i = 0; i < nums.size(); i++) {
            // make a choice
            track.push_back(nums[i]);
            // enter the next level of backtracking tree
            backtrack(nums);
            // undo the choice
            track.pop_back();
        }
    }
};

python 🤖

class Solution:
    
    def __init__(self):
        self.res = []
        self.track = []
    
    def permuteRepeat(self, nums: List[int]) -> List[List[int]]:
        self.backtrack(nums)
        return self.res

    # core function of backtracking algorithm
    def backtrack(self, nums: List[int]) -> None:
        # base case, reach the leaf node
        if len(self.track) == len(nums):
            # collect the value at the leaf node
            self.res.append(self.track[:])
            return

        # standard framework of backtracking algorithm
        for i in range(len(nums)):
            # make a choice
            self.track.append(nums[i])
            # go to the next level of the backtracking tree
            self.backtrack(nums)
            # unmake the choice
            self.track.pop()

go 🤖

func permuteRepeat(nums []int) [][]int {
    var res [][]int
    var track []int
    
    backtrack(nums, &res, track)
    
    return res
}

// core function of backtracking algorithm
func backtrack(nums []int, res *[][]int, track []int) {
    // base case, reach the leaf node
    if len(track) == len(nums) {
        // collect the value at the leaf node
        tmp := make([]int, len(track))
        copy(tmp, track)
        *res = append(*res, tmp)
        return
    }

    // standard framework of backtracking algorithm
    for i := 0; i < len(nums); i++ {
        // make a choice
        track = append(track, nums[i])
        // go to the next level of the backtracking tree
        backtrack(nums, res, track)
        // undo the choice
        track = track[:len(track)-1]
    }
}

javascript 🤖

var permuteRepeat = function(nums) {
    let res = [];
    let track = [];
    
    backtrack(nums, track, res);
    return res;
};

// backtracking core function
var backtrack = function(nums, track, res) {
    // base case, reach the leaf node
    if (track.length === nums.length) {
        // collect the values on the leaf node
        res.push([...track]);
        return;
    }

    // standard framework of backtracking algorithm
    for (let i = 0; i < nums.length; i++) {
        // make a choice
        track.push(nums[i]);
        // go to the next level of backtracking tree
        backtrack(nums, track, res);
        // cancel the choice
        track.pop();
    }
};

With this, all nine variations of permutation/combination/subset problems have been covered.

Final Summary

Let's review the differences in code for the three forms of permutation/combination/subset problems.

Since subset and combination problems are essentially the same, with only slight differences in the base case, we'll look at these two problems together.

Form 1: Elements are unique and non-reusable, meaning each element in nums is unique and can be used at most once. The core backtrack code is as follows:

java 🟢

// Backtracking algorithm framework for combination/subset problems
void backtrack(int[] nums, int start) {
    // Standard backtracking algorithm framework
    for (int i = start; i < nums.length; i++) {
        // Make a choice
        track.addLast(nums[i]);
        // Note the parameter
        backtrack(nums, i + 1);
        // Undo the choice
        track.removeLast();
    }
}

// Backtracking algorithm framework for permutation problems
void backtrack(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        // Pruning logic
        if (used[i]) {
            continue;
        }
        // Make a choice
        used[i] = true;
        track.addLast(nums[i]);

        backtrack(nums);
        // Undo the choice
        track.removeLast();
        used[i] = false;
    }
}

cpp 🤖

// Backtracking algorithm framework for combination/subset problems
void backtrack(vector<int>& nums, int start) {
    // Standard backtracking algorithm framework
    for (int i = start; i < nums.size(); i++) {
        // Make a choice
        track.push_back(nums[i]);
        // Note the parameter
        backtrack(nums, i + 1);
        // Undo the choice
        track.pop_back();
    }
}

// Backtracking algorithm framework for permutation problems
void backtrack(vector<int>& nums) {
    for (int i = 0; i < nums.size(); i++) {
        // Pruning logic
        if (used[i]) {
            continue;
        }
        // Make a choice
        used[i] = true;
        track.push_back(nums[i]);
        backtrack(nums);
        // Undo the choice
        track.pop_back();
        used[i] = false;
    }
}

python 🤖

# Backtracking algorithm framework for combination/subset problems
def backtrack(nums: List[int], start: int):
    # Standard backtracking algorithm framework
    for i in range(start, len(nums)):
        # Make a choice
        track.append(nums[i])
        # Note the parameter
        backtrack(nums, i + 1)
        # Undo the choice
        track.pop()

# Backtracking algorithm framework for permutation problems
def backtrack(nums: List[int]):
    for i in range(len(nums)):
        # Pruning logic
        if used[i]:
            continue
        # Make a choice
        used[i] = True
        track.append(nums[i])

        backtrack(nums)
        # Undo the choice
        track.pop()
        used[i] = False

go 🤖

// Backtracking algorithm framework for combination/subset problems 
func backtrack(nums []int, start int) {
    // Standard backtracking algorithm framework 
    for i := start; i < len(nums); i++ {
        // Make a choice
        track = append(track, nums[i])
        // Note the parameter 
        backtrack(nums, i+1)
        // Undo the choice 
        track = track[:len(track)-1]
    }
}

// Backtracking algorithm framework for permutation problems
func backtrack(nums []int) {
    for i := 0; i < len(nums); i++ {
        // Pruning logic 
        if used[i] {
            continue
        }
        // Make a choice 
        used[i] = true
        track = append(track, nums[i])

        backtrack(nums)
        // Undo the choice 
        track = track[:len(track)-1]
        used[i] = false
    }
}

javascript 🤖

// Backtracking algorithm framework for combination/subset problems
var backtrack = function(nums, start) {
    // Standard backtracking algorithm framework
    for (var i = start; i < nums.length; i++) {
        // Make a choice
        track.addLast(nums[i]);
        // Note the parameter
        backtrack(nums, i + 1);
        // Undo the choice
        track.removeLast();
    }
}

// Backtracking algorithm framework for permutation problems
var backtrack = function(nums) {
    for (var i = 0; i < nums.length; i++) {
        // Pruning logic
        if (used[i]) {
            continue;
        }
        // Make a choice
        used[i] = true;
        track.addLast(nums[i]);

        backtrack(nums);
        // Undo the choice
        track.removeLast();
        used[i] = false;
    }
}

Form 2: Elements can be repeated but not reusable, meaning elements in nums can be duplicated, but each element can only be used once. The key lies in sorting and pruning. The core backtrack code is as follows:

java 🟢

Arrays.sort(nums);
// backtracking algorithm framework for combination/subset problems
void backtrack(int[] nums, int start) {
    // standard backtracking algorithm framework
    for (int i = start; i < nums.length; i++) {
        // pruning logic, skip the adjacent branches with the same value
        if (i > start && nums[i] == nums[i - 1]) {
            continue;
        }
        // make a choice
        track.addLast(nums[i]);
        // note the parameter
        backtrack(nums, i + 1);
        // undo the choice
        track.removeLast();
    }
}


Arrays.sort(nums);
// backtracking algorithm framework for permutation problems
void backtrack(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        // pruning logic
        if (used[i]) {
            continue;
        }
        // pruning logic, fix the relative position of the same elements in the permutation
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
            continue;
        }
        // make a choice
        used[i] = true;
        track.addLast(nums[i]);

        backtrack(nums);
        // undo the choice
        track.removeLast();
        used[i] = false;
    }
}

cpp 🤖

sort(nums.begin(), nums.end());
// Backtracking algorithm framework for combination/subset problems
void backtrack(vector<int>& nums, int start) {
    // Standard framework of backtracking algorithm
    for (int i = start; i < nums.size(); i++) {
        // Pruning logic, skip adjacent branches with the same value
        if (i > start && nums[i] == nums[i - 1]) {
            continue;
        }
        // Make a choice
        track.push_back(nums[i]);
        // Note the parameters
        backtrack(nums, i + 1);
        // Undo the choice
        track.pop_back();
    }
}

sort(nums.begin(), nums.end());
// Backtracking algorithm framework for permutation problems
void backtrack(vector<int>& nums, vector<bool>& used) {
    for (int i = 0; i < nums.size(); i++) {
        // Pruning logic
        if (used[i]) {
            continue;
        }
        // Pruning logic, fix the relative position of the same elements in the permutation
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
            continue;
        }
        // Make a choice
        used[i] = true;
        track.push_back(nums[i]);

        backtrack(nums, used);
        // Undo the choice
        track.pop_back();
        used[i] = false;
    }
}

python 🤖

nums.sort()
# Backtracking algorithm framework for combination/substring problem
def backtrack(nums: List[int], start: int):
    # Standard backtracking algorithm framework
    for i in range(start, len(nums)):
        # Pruning logic, skip adjacent branches with the same value
        if i > start and nums[i] == nums[i - 1]:
            continue
        # Make a choice
        track.append(nums[i])
        # Note the parameters
        backtrack(nums, i + 1)
        # Undo the choice
        track.pop()


nums.sort()
# Backtracking algorithm framework for permutation problem
def backtrack(nums: List[int]):
    for i in range(len(nums)):
        # Pruning logic
        if used[i]:
            continue
        # Pruning logic, fix the relative position of the same elements in the permutation
        if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
            continue
        # Make a choice
        used[i] = True
        track.append(nums[i])

        backtrack(nums)
        # Undo the choice
        track.pop()
        used[i] = False

go 🤖

sort.Ints(nums)
// Backtracking algorithm framework for combination/subset problems
func backtrack(nums []int, start int) {
    // Standard backtracking algorithm framework
    for i := start; i < len(nums); i++ {
        // Pruning logic, skip adjacent branches with the same value
        if i > start && nums[i] == nums[i-1] {
            continue
        }
        // Make a choice
        track = append(track, nums[i])
        // Note the parameter
        backtrack(nums, i+1)
        // Undo the choice
        track = track[:len(track)-1]
    }
}


sort.Ints(nums)
// Backtracking algorithm framework for permutation problems
func backtrack(nums []int) {
    for i := 0; i < len(nums); i++ {
        // Pruning logic
        if used[i] {
            continue
        }
        // Pruning logic, fix the relative positions of the same elements in the permutation
        if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
            continue
        }
        // Make a choice
        used[i] = true
        track = append(track, nums[i])

        backtrack(nums)

        // Undo the choice
        track = track[:len(track)-1]
        used[i] = false
    }
}

javascript 🤖

nums.sort((a, b) => a - b);
// backtracking algorithm framework for combination/subset problems
var backtrack = function(nums, start) {
    // standard backtracking algorithm framework
    for (var i = start; i < nums.length; i++) {
        // pruning logic, skip the adjacent branches with the same value
        if (i > start && nums[i] === nums[i - 1]) {
            continue;
        }
        // make a choice
        track.add(nums[i]);
        // note the parameters
        backtrack(nums, i + 1);
        // undo the choice
        track.pop();
    }
}

nums.sort((a, b) => a - b);
// backtracking algorithm framework for permutation problems
var backtrack = function(nums) {
    for (var i = 0; i < nums.length; i++) {
        // pruning logic
        if (used[i]) {
            continue;
        }
        // pruning logic, fix the relative position of the same elements in the permutation
        if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) {
            continue;
        }
        // make a choice
        used[i] = true;
        track.add(nums[i]);

        backtrack(nums);
        // undo the choice
        track.pop();
        used[i] = false;
    }
}

Form Three: Elements are Unique and Can Be Repeated, meaning all elements in nums are unique and each element can be used multiple times. Simply remove the deduplication logic. The core code for backtrack is as follows:

java 🟢

// Backtracking algorithm framework for combination/subset problems
void backtrack(int[] nums, int start) {
    // Standard backtracking algorithm framework
    for (int i = start; i < nums.length; i++) {
        // Make a choice
        track.addLast(nums[i]);
        // Note the parameter
        backtrack(nums, i);
        // Undo the choice
        track.removeLast();
    }
}

// Backtracking algorithm framework for permutation problems
void backtrack(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        // Make a choice
        track.addLast(nums[i]);
        backtrack(nums);
        // Undo the choice
        track.removeLast();
    }
}

cpp 🤖

// Backtracking algorithm framework for combination/subset problems
void backtrack(vector<int>& nums, int start, deque<int>& track) {
    // Standard backtracking algorithm framework
    for (int i = start; i < nums.size(); i++) {
        // Make a choice
        track.push_back(nums[i]);
        // Note the parameters
        backtrack(nums, i, track);
        // Undo the choice
        track.pop_back();
    }
}

// Backtracking algorithm framework for permutation problems
void backtrack(vector<int>& nums, deque<int>& track) {
    for (int i = 0; i < nums.size(); i++) {
        // Make a choice
        track.push_back(nums[i]);
        backtrack(nums, track);
        // Undo the choice
        track.pop_back();
    }
}

python 🤖

# Backtracking algorithm framework for combination/subset problems
def backtrack(nums: List[int], start: int):
    # Standard framework for backtracking algorithm
    for i in range(start, len(nums)):
        # Make a choice
        track.append(nums[i])
        # Note the parameter
        backtrack(nums, i)
        # Undo the choice
        track.pop()


# Backtracking algorithm framework for permutation problems
def backtrack(nums: List[int]):
    for i in range(len(nums)):
        # Make a choice
        track.append(nums[i])
        backtrack(nums)
        # Undo the choice
        track.pop()

go 🤖

// Backtracking algorithm framework for combination/subset problems
func backtrack(nums []int, start int) {
    // Standard backtracking algorithm framework
    for i := start; i < len(nums); i++ {
        // Make a choice
        track = append(track, nums[i])
        // Note the parameter
        backtrack(nums, i)
        // Undo the choice
        track = track[:len(track)-1]
    }
}

// Backtracking algorithm framework for permutation problems
func backtrack(nums []int) {
    for i := 0; i < len(nums); i++ {
        // Make a choice
        track = append(track, nums[i])
        backtrack(nums)
        // Undo the choice
        track = track[:len(track)-1]
    }
}

javascript 🤖

// Backtracking algorithm framework for combination/subset problems
var backtrack = function(nums, start) {
    // Standard backtracking algorithm framework
    for (var i = start; i < nums.length; i++) {
        // Make a choice
        track.add(nums[i]);
        // Note the parameter
        backtrack(nums, i);
        // Undo the choice
        track.pop();
    }
};

// Backtracking algorithm framework for permutation problems
var backtrack = function(nums) {
    // Backtracking algorithm framework for permutation problems
    for (var i = 0; i < nums.length; i++) {
        // Make a choice
        track.add(nums[i]);
        backtrack(nums);
        // Undo the choice
        track.pop();
    }
};

By thinking from the perspective of trees, these problems may seem complex and varied, but in reality, they can be solved by simply modifying the base case. This is why I emphasize the importance of tree-related problems in Framework Thinking for Learning Algorithms and Data Structures and A Step-by-Step Guide to Binary Trees (Overview).

If you've made it this far, you deserve a round of applause. I believe that in the future, when you encounter various confusing algorithm problems, you'll be able to see through their essence and handle them with ease. Additionally, due to space constraints, this article does not include complexity analysis of these algorithms. You can use the complexity analysis methods I discussed in A Practical Guide to Algorithm Time and Space Complexity Analysis to try analyzing their complexities yourself.

引用本文的题目

安装我的 Chrome 刷题插件点开下列题目可直接查看解题思路：

LeetCode	力扣
1079. Letter Tile Possibilities	1079. 活字印刷
131. Palindrome Partitioning	131. 分割回文串
17. Letter Combinations of a Phone Number	17. 电话号码的字母组合
254. Factor Combinations🔒	254. 因子的组合🔒
267. Palindrome Permutation II🔒	267. 回文排列 II🔒
368. Largest Divisible Subset	368. 最大整除子集
491. Non-decreasing Subsequences	491. 递增子序列
638. Shopping Offers	638. 大礼包
967. Numbers With Same Consecutive Differences	967. 连续差相同的数字
996. Number of Squareful Arrays	996. 正方形数组的数目
-	剑指 Offer 38. 字符串的排列
-	剑指 Offer II 079. 所有子集
-	剑指 Offer II 080. 含有 k 个元素的组合
-	剑指 Offer II 081. 允许重复选择元素的组合
-	剑指 Offer II 083. 没有重复元素集合的全排列

回溯算法秒杀所有排列-组合-子集问题

216. 组合总和 III https://leetcode.cn/problems/combination-sum-iii

216. Combination Sum III https://leetcode.com/problems/combination-sum-iii

39. 组合总和 https://leetcode.cn/problems/combination-sum

39. Combination Sum https://leetcode.com/problems/combination-sum

40. 组合总和 II https://leetcode.cn/problems/combination-sum-ii

40. Combination Sum II https://leetcode.com/problems/combination-sum-ii

46. 全排列 https://leetcode.cn/problems/permutations

46. Permutations https://leetcode.com/problems/permutations

47. 全排列 II https://leetcode.cn/problems/permutations-ii

47. Permutations II https://leetcode.com/problems/permutations-ii

77. 组合 https://leetcode.cn/problems/combinations

77. Combinations https://leetcode.com/problems/combinations

78. 子集 https://leetcode.cn/problems/subsets

78. Subsets https://leetcode.com/problems/subsets

90. 子集 II https://leetcode.cn/problems/subsets-ii

90. Subsets II https://leetcode.com/problems/subsets-ii

剑指 Offer II 079. 所有子集 https://leetcode.cn/problems/TVdhkn

剑指 Offer II 079. 所有子集 https://leetcode.com/problems/TVdhkn

剑指 Offer II 080. 含有 k 个元素的组合 https://leetcode.cn/problems/uUsW3B

剑指 Offer II 080. 含有 k 个元素的组合 https://leetcode.com/problems/uUsW3B

剑指 Offer II 081. 允许重复选择元素的组合 https://leetcode.cn/problems/Ygoe9J

剑指 Offer II 081. 允许重复选择元素的组合 https://leetcode.com/problems/Ygoe9J

剑指 Offer II 082. 含有重复元素集合的组合 https://leetcode.cn/problems/4sjJUc

剑指 Offer II 082. 含有重复元素集合的组合 https://leetcode.com/problems/4sjJUc

剑指 Offer II 083. 没有重复元素集合的全排列 https://leetcode.cn/problems/VvJkup

剑指 Offer II 083. 没有重复元素集合的全排列 https://leetcode.com/problems/VvJkup

剑指 Offer II 084. 含有重复元素集合的全排列 https://leetcode.cn/problems/7p8L0Z

剑指 Offer II 084. 含有重复元素集合的全排列 https://leetcode.com/problems/7p8L0Z

Subsets (Elements Are Unique and Non-repeating)

Combinations (Elements are Unique and Non-repetitive)

Permutations (Elements are Unique and Non-repetitive)

Subsets/Combinations (Elements Can Repeat but Not Re-selectable)

Permutations (Elements Can Repeat, No Repetition Allowed)

Subsets/Combinations (Elements are Unique and Can Be Repeated)

Permutations (Elements are Unique and Can Be Repeated)

Final Summary