Backtracking Algorithm to Solve All Permutation/Combination/Subset Problems

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, the problem can include various constraints, such as finding a combination of elements that sum to a target with exactly k elements. This leads to many variations, which is why permutation and combination questions are frequently tested in interviews and exams.

Regardless of how the form changes, the essence is to enumerate all solutions, which naturally form a tree structure. By effectively using the backtracking algorithm framework and slightly modifying the code framework, you can tackle these problems comprehensively.

Specifically, you need to first read and understand the earlier article Core Techniques of Backtracking Algorithms. Then, by remembering the backtracking trees for the subset and permutation problems, you can solve all permutation, combination, and subset-related problems:

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

Firstly, combination problems and subset problems are actually equivalent, as will be explained later. As for the three variations mentioned earlier, they are merely modifications of these two trees, either by pruning or adding branches.

Next, we will enumerate all 9 forms of permutation/combination/subset problems and learn how to use the backtracking algorithm to handle them effectively.

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:

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

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

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

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

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] ]

Let's set aside the coding part for now and recall our high school knowledge on how to manually derive all subsets.

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

Next, based on S_0, generate all subsets with 1 element, which I will refer to as S_1:

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

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

This is because the order of elements in a set does not matter. In [1,2,3], after 2, there is only 3. If you add the preceding 1, then [2,1] would duplicate the earlier subset [1,2].

In other words, by maintaining the relative order of elements, we prevent duplicate subsets from appearing.

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].

This entire derivation process forms a tree:

Note the characteristics of this tree:

If the root node is considered as level 0, and the elements on the branches between each node and the root node are taken as the value of that node, then all nodes at level n represent all subsets of size n.

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

So, to calculate all subsets, you simply need to traverse this multi-branch tree and collect the values of all nodes, right?

Let's look at the code:

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>> subsets(int[] nums) {
        backtrack(nums, 0);
        return res;
    }

    // the core function of backtracking algorithm,
    // traversing the backtracking tree of subset
    void backtrack(int[] nums, int start) {

        // the pre-order position, the value of each node is a subset
        res.add(new LinkedList<>(track));
        
        // the standard framework of backtracking algorithm
        for (int i = start; i < nums.length; i++) {
            // make a choice
            track.addLast(nums[i]);
            // control the traversal of branches through
            // the start parameter to avoid generating
            backtrack(nums, i + 1);
            // undo the choice
            track.removeLast();
        }
    }
}

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

public:
    // main function
    vector<vector<int>> subsets(vector<int>& nums) {
        backtrack(nums, 0);
        return res;
    }

    // the core function of backtracking algorithm,
    // traverse the backtracking tree of subset
    void backtrack(vector<int>& nums, int start) {

        // preorder position, the value of each node is a subset
        res.push_back(track);

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

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

    # main function
    def subsets(self, nums: List[int]) -> List[List[int]]:
        self.backtrack(nums, 0)
        return self.res
    
    # core function of backtracking algorithm, traverse the backtracking tree of subset problem
    def backtrack(self, nums: List[int], start: int) -> None:
        
        # pre-order position, the value of each node is a subset
        self.res.append(list(self.track))
        
        # standard framework of backtracking algorithm
        for i in range(start, len(nums)):
            # make a choice
            self.track.append(nums[i])
            # control the traversal of branches through
            # the start parameter to avoid generating
            self.backtrack(nums, i + 1)
            # undo the choice
            self.track.pop()

func subsets(nums []int) [][]int {
    var res [][]int
    // record the recursive path of backtracking algorithm
    var track []int
    
    // the core function of backtracking algorithm,
    // traverse the backtracking tree of subset
    var backtrack func(int)
    backtrack = func(start int) {
        // pre-order position, the value of each node is a subset
        res = append(res, append([]int(nil), track...))
        
        // standard framework of backtracking algorithm
        for i := start; i < len(nums); i++ {
            // make a choice
            track = append(track, nums[i])
            // control the traversal of branches through
            // the start parameter to avoid generating
            backtrack(i + 1)
            // undo the choice
            track = track[:len(track)-1]
        }
    }

    backtrack(0)
    return res
}

var subsets = function(nums) {
    // used to store the result
    const res = [];
    // used to record the backtracking path
    const track = [];
    
    // the core function of backtracking algorithm,
    // traverse the backtracking tree of subset
    const backtrack = (start) => {
        // the position of preorder traversal, the value of each node is a subset
        res.push([...track]);
        
        // the standard framework of backtracking algorithm
        for (let i = start; i < nums.length; i++) {
            // make a choice
            track.push(nums[i]);
            // backtracking to traverse the next level node
            backtrack(i + 1);
            // undo the choice
            track.pop();
        }
    };
    
    backtrack(0);
    return res;
};

Readers who have read the previous article Core Framework of Backtracking Algorithm should find it easy to understand this code. We use the start parameter to control the growth of branches, avoiding the creation of duplicate subsets. The track variable records the path values from the root node to each node. At the pre-order position, we collect the path values of each node, and once the traversal of the backtracking tree is completed, all subsets are collected:

Finally, at the beginning of the backtrack function, it might seem like there is no base case, which raises the question of whether it could lead to infinite recursion.

In fact, it will not. When start == nums.length, the value of the leaf node will be added to res, but the for loop will not execute, which ends the recursion.

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:

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

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

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

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

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 if I translate it for you, it becomes a subset problem:

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

Taking nums = [1,2,3] as an example again, previously you were asked to find all subsets by collecting the values of all nodes. Now you only need to collect the nodes at level 2 (considering the root node as level 0), which results in 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 of nodes only at level k:

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
            backtrack(i + 1, n, k);
            // undo the choice
            track.removeLast();
        }
    }
}

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
            backtrack(i + 1, n, k);
            // undo the choice
            track.pop_back();
        }
    }
};

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
            self.backtrack(i + 1, n, k)
            # undo the choice
            self.track.pop()

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
            backtrack(i + 1)
            // undo the choice
            track = track[:len(track)-1]
        }
    }

    backtrack(1)
    return res
}

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

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

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

from typing import List

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

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

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]
]

The combination/subset problem we discussed earlier uses a start variable to ensure that after the element nums[start], only elements from nums[start+1..] will appear. This ensures that there are no duplicate subsets by fixing the relative position of elements.

However, permutation problems require you to exhaustively list element positions, and elements to the left of nums[i] can appear after nums[i]. Thus, the previous method doesn't work, and an additional used array is needed to mark which elements can still be selected.

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

We use the used array to mark elements that are already on the path to avoid duplicate selection. Then, we collect the values at all leaf nodes to get all permutation results:

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;
        }
    }
}

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;
        }
    }
};

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

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
    }
}

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:

// 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);
        // ...
    }
}

// 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);
        // ...
    }
}

# 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)
        # ...

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)
        // ...
    }
}

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

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

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

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

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

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 is stated this way, let's set aside that detail and focus on solving the problem.

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

Drawing the tree structure of subsets based on our previous approach, it's clear that adjacent branches with the same value will lead to duplicates:

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

You can see that [2] and [1, 2] appear as duplicates, so we need to prune the tree. If a node has multiple adjacent branches with the same value, only the first branch should be explored; the rest should be pruned and not traversed:

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:

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
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            track.addLast(nums[i]);
            backtrack(nums, i + 1);
            track.removeLast();
        }
    }
}

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
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            track.push_back(nums[i]);
            backtrack(nums, i + 1);
            track.pop_back();
        }
    }
};

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
            if i > start and nums[i] == nums[i - 1]:
                continue
            self.track.append(nums[i])
            self.backtrack(nums, i + 1)
            self.track.pop()

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
        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]
    }
}

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

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];
        }
    }
}

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];
        }
    }
};

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]

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]
    }
}

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:

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

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

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

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

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:

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
            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;
        }
    }
}

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
            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;
        }
    }
};

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

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
        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
    }
}

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

1. The nums array is sorted.
2. 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, for example, if the input is nums = [1,2,2',2''], 2' will only be selected if 2 has already been used, and similarly, 2'' will only be selected if 2' has been used. This ensures that the relative positions of identical elements in the permutation remain fixed.

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

This modification does not cause errors because it effectively maintains the relative order of 2'' -> 2' -> 2, ultimately achieving the effect of removing duplicates.

But why does this reduce efficiency? Because this approach does not prune as many branches.

For instance, with the input nums = [2,2',2''], the resulting backtracking tree is as follows:

If green branches represent paths traversed by the backtrack function, and red branches represent triggered 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 results in a clean cut, whereas the used[i - 1] logic can also achieve a duplicate-free result, but it prunes fewer branches and involves more redundant calculations, thus being less efficient.

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

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

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;
    }
}

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;
    }
}

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

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
    }
}