回溯

注意

  1. 回溯是递归的副产品，只要有递归就会有回溯。
  2. 回溯法就是暴力搜索，遍历出所有可选列表。
  3. 每一道回溯法的题目都可以抽象为树形结构。

待做事项&&疑问

  1. 回溯题目常参考灵茶山艾府(以下简称灵神)的代码，发现灵神常用五个参数，与代码框架中的不同，需要比对这其中的差距。

代码框架（必背）

注意，本文涉及到回溯的代码都会用该框架来写！！但不会创建像下面这么多的函数，因为只有一两行代码。

详见 《Hello 算法》：在二叉树中搜索所有值为 7 的节点，请返回根节点到这些节点的路径，并要求路径中不包含值为 3 的节点。

Shut up and calculate! -David Mermin && Feynman

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// 状态 state 为节点遍历路径，选择 choices 为当前节点的左子节点和右子节点，结果 res 是路径列表
/* 判断当前状态是否为解 */
boolean isSolution(List<TreeNode> state) {
    return !state.isEmpty() && state.get(state.size() - 1).val == 7;
}

/* 记录解 */
void recordSolution(List<TreeNode> state, List<List<TreeNode>> res) {
    res.add(new ArrayList<>(state));
}

/* 判断在当前状态下，该选择是否合法 */
boolean isValid(List<TreeNode> state, TreeNode choice) {
    return choice != null && choice.val != 3;
}

/* 更新状态 */
void makeChoice(List<TreeNode> state, TreeNode choice) {
    state.add(choice);
}

/* 恢复状态 */
void undoChoice(List<TreeNode> state, TreeNode choice) {
    state.remove(state.size() - 1);
}

/* 回溯算法：例题三 */
void backtrack(List<TreeNode> state, List<TreeNode> choices, List<List<TreeNode>> res) {
    // 检查是否为解
    if (isSolution(state)) {
        // 记录解
        recordSolution(state, res);
    }
    // 遍历所有选择
    for (TreeNode choice : choices) {
        // 剪枝：检查选择是否合法
        if (isValid(state, choice)) {
            // 尝试：做出选择，更新状态
            makeChoice(state, choice);
            // 进行下一轮选择
            backtrack(state, Arrays.asList(choice.left, choice.right), res);
            // 回退：撤销选择，恢复到之前的状态
            undoChoice(state, choice);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void backtrack(List<TreeNode> state, List<TreeNode> choices, List<List<TreeNode>> res) {
    // 检查是否为解
    if (!state.isEmpty() && state.get(state.size() - 1).val == 7) {
        // 记录解
        res.add(new ArrayList<>(state));
    }
    // 遍历所有选择
    for (TreeNode choice : choices) {
        // 剪枝：检查选择是否合法
        if (choice != null && choice.val != 3) {
            // 尝试：做出选择，更新状态
            state.add(choice);
            // 进行下一轮选择
            backtrack(state, Arrays.asList(choice.left, choice.right), res);
            // 回退：撤销选择，恢复到之前的状态
            state.remove(state.size() - 1);
        }
    }
}

共有七步：检查是否为解、记录解、遍历所有选择、剪枝(检查选择是否合法)、尝试(做出选择,更新状态)、进行下一轮选择、回退(撤销选择)

背诵口诀：简(检)记便(遍)笺(剪)常(尝)晋(进)会(回)：简单记录在便笺上，常晋集团要开会

77. 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

示例 2：

1
2
输入：n = 1, k = 1
输出：[[1]]

提示：

  • 1 <= n <= 20
  • 1 <= k <= n 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    private List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        getCombine(n, k, 1, new ArrayList<>());
        return ans;
    }
    
    public void getCombine(int n, int k, int start, List<Integer> list) {
        // 检查是否为解
        if(k == 0) {
            // 记录解
            ans.add(new ArrayList<>(list));
            return;
        }
        // 遍历所有选择
        for(int i = start;i <= n - k + 1;i++) {
            // 尝试：做出选择，更新状态
            list.add(i);
            // 进行下一轮选择
            getCombine(n, k - 1, i+1, list);
            // 回退：撤销选择，恢复到之前的状态
            list.remove(list.size() - 1);
        }
    }
}

216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

  • 只使用数字1到9
  • 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:

1
2
3
4
5
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:

1
2
3
4
5
6
7
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

示例 3:

1
2
3
4
输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>(k);
        dfs(9, n, k, ans, path); // 从 i=9 开始倒着枚举
        return ans;
    }

    private void dfs(int i, int leftSum, int k, List<List<Integer>> ans, List<Integer> path) {
        int d = k - path.size(); // 还要选 d 个数
        if (leftSum == 0 && d == 0) { // 找到一个合法组合
            ans.add(new ArrayList<>(path));
            return;
        }
        // 枚举的数不能太小，否则后面没有数可以选
        for (int j = i; j >= d; j--) {
            if (leftSum < 0 || leftSum > (i * 2 - d + 1) * d / 2) { // 剪枝
                return;
            }
            path.add(j);
            dfs(j - 1, leftSum - j, k, ans, path);
            path.removeLast(); // path.remove(path.size() - 1);
        }
    }
}

// 将剪枝操作提前，在进行检查是否为解判断时可以少判断条件
class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>(k);
        dfs(9, n, k, ans, path); // 从 i=9 开始倒着枚举
        return ans;
    }

    private void dfs(int i, int leftSum, int k, List<List<Integer>> ans, List<Integer> path) {
        int d = k - path.size(); // 还要选 d 个数

        if (leftSum < 0 || leftSum > (i * 2 - d + 1) * d / 2) { // 剪枝
            return;
        }
        if (d == 0) { // 找到一个合法组合
            ans.add(new ArrayList<>(path));
            return;
        }
        // 枚举的数不能太小，否则后面没有数可以选
        for (int j = i; j >= d; j--) {
            path.add(j);
            dfs(j - 1, leftSum - j, k, ans, path);
            path.removeLast(); // path.remove(path.size() - 1);
        }
    }
}

注意

这里的回溯代码，剪枝操作放在了检查是否为解之前；需要总结在什么情况下剪枝操作要提前？

剪枝操作中包含的参数影响检查是否为解的判断时要把剪枝操作提前

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

img

示例 1：

1
2
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

1
2
输入：digits = "2"
输出：["a","b","c"]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    private static final String[] MAPPING = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    public List<String> letterCombinations(String digits) {
        int n = digits.length();
        if (n == 0) {
            return List.of();
        }

        List<String> ans = new ArrayList<>();
        char[] path = new char[n]; // 注意 path 长度一开始就是 n，不是空数组
        dfs(0, ans, path, digits.toCharArray());
        return ans;
    }

    private void dfs(int i, List<String> ans, char[] path, char[] digits) {
        if (i == digits.length) {
            ans.add(new String(path));
            return;
        }
        String letters = MAPPING[digits[i] - '0'];
        for (char c : letters.toCharArray()) {
            path[i] = c; // 直接覆盖
            dfs(i + 1, ans, path, digits);
        }
    }
}

注意

此处回溯代码代码不需要回退，因为采用的是固定数组，每次重新选择都会覆盖之前的值

使用 ArrayList（需要回退）
1
2
3
4
5
6
7
8
9
10
11
递归树：
            []
      /     |     \
    [a]    [b]    [c]      // path 长度 = 1
   /  \    /  \    /  \
 [ad][ae][bd][be][cd][ce]   // path 长度 = 2

// 如果不回退：
从 [a] 到 [ad]：path = [a,d]
回溯到 [a] 时，如果不删除 'd'：path = [a,d] 长度2
尝试 'e'：path.add('e') → [a,d,e] 长度3 ❌ 错误！
使用固定数组（不需要回退）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
char[] path = new char[2];  // 固定长度2

递归树：
dfs(0): path[0] = 'a'  → path = ['a', _ ]
  dfs(1): path[1] = 'd' → path = ['a','d']
  得到 "ad"
  
回溯到 dfs(0)：
  不需要删除！因为 path[1] 的值 'd' 会被下一轮覆盖
  
dfs(0): path[0] = 'b'  → path = ['b','d']  // 覆盖了 path[0]
  dfs(1): path[1] = 'd' → path = ['b','d']
  得到 "bd"
  
// path[1] 的 'd' 不会被自动清除，但会被覆盖

39. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

1
2
3
4
5
6
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

1
2
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

1
2
输入: candidates = [2], target = 1
输出: []
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(0, target, candidates, ans, path);
        return ans;
    }

    private void dfs(int i, int left, int[] candidates, List<List<Integer>> ans, List<Integer> path) {
        if (left == 0) {
            // 找到一个合法组合
            ans.add(new ArrayList<>(path));
            return;
        }

        // 枚举选哪个
        for (int j = i; j < candidates.length; j++) {
            if (candidates[j] <= left){
                path.add(candidates[j]);
                dfs(j, left - candidates[j], candidates, ans, path);
                path.remove(path.size() - 1); // 恢复现场
            }
        }
    }
}

40. 组合总和 II

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

示例 1:

1
2
3
4
5
6
7
8
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

1
2
3
4
5
6
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(0, target, candidates, ans, path);
        return ans;
    }

    private void dfs(int i, int left, int[] candidates, List<List<Integer>> ans, List<Integer> path) {
        if (left == 0) {
            // 找到一个合法组合
            ans.add(new ArrayList<>(path));
            return;
        }

        for (int j = i; j < candidates.length && candidates[j] <= left; j++) {
            if (j > i && candidates[j] == candidates[j - 1]) {
                continue;
            }
            path.add(candidates[j]);
            dfs(j + 1, left - candidates[j], candidates, ans, path);
            path.remove(path.size() - 1); // 恢复现场
        }
    }
}

注意

与 组合总和 相比，这里的剪枝更为复杂，所以对遍历之中和尝试之前的逻辑进行了修改，本质上还是剪枝

131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例 1：

1
2
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

1
2
输入：s = "a"
输出：[["a"]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> ans = new ArrayList<>();
        List<String> path = new ArrayList<>();
        dfs(0, s, path, ans);
        return ans;
    }


    // 标准回溯模块代码
    private void dfs(int i, String s, List<String> path, List<List<String>> ans) {
        if (i == s.length()) { // s 分割完毕
            ans.add(new ArrayList<>(path)); // 复制 path
            return;
        }
        for (int j = i; j < s.length(); j++) { // 枚举子串的结束位置
            if (isPalindrome(s, i, j)) { // 判断 [i, j] 是不是回文串
                path.add(s.substring(i, j + 1)); // 分割！
                // 现在 s 未被分割的部分为 [j+1, n-1]
                dfs(j + 1, s, path, ans);
                path.removeLast(); // path.remove(path.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) {
                return false;
            }
        }
        return true;
    }
}

93. 复原 IP 地址

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

  • 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：

1
2
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

1
2
输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

1
2
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public List<String> restoreIpAddresses(String s) {
        int n = s.length();
        List<String> ans = new ArrayList<>();
        String[] path = new String[4];
        dfs(0, 0, s, s.length(), path, ans);
        return ans;
    }

    // 分割 s[i] 到 s[n-1]，现在在第 j 段（j 从 0 开始）
    private void dfs(int i, int j, String s, int n, String[] path, List<String> ans) {
        // 剪枝：还剩下 n-i 个字符，需要分成 4-j 段，每段至少 1 个字符，至多 3 个字符，所以 4-j <= n-i <= (4-j)*3
        if (n - i < 4 - j || n - i > (4 - j) * 3) {
            return;
        }

        if (i == n) { // s 分割完毕
            ans.add(String.join(".", path));
            return;
        }

        // 子串左端点为 i
        // 枚举子串右端点 right
        int ipVal = 0;
        for (int right = i; right < n; right++) {
            ipVal = ipVal * 10 + (s.charAt(right) - '0');
            if (ipVal > 255 || ) { // 不合法
                break;
            }
            path[j] = s.substring(i, right + 1); // 直接覆盖 path[j]，无需恢复现场
            dfs(right + 1, j + 1, s, n, path, ans);
            if (ipVal == 0) { // 前导零，对于后续循环不合法
                break;
            }
        }
    }
}

注意

该题目涉及到的剪枝操作过多，在实际中如果没记住可不考虑做出

步骤图解

递归过程较长，只显示前面的内容

例子： s = "255255"

目标：分割成 4 个 0–255 之间的数字，且不能有前导零（除非本身就是 “0”）。

初始调用

1
dfs(i=0, j=0, s="255255", n=6)

此时 n - i = 6，4 - j = 4，(4 - j) * 3 = 12，满足：
4 <= 6 <= 12 ✅

第一层 (j=0, 枚举第 1 段)

s = “255255”, i = 0 开始枚举 right

right = 0

子串 "2"
ipVal = 0*10 + 2 = 2
2 <= 255 ✅
path[0] = "2"
进入 dfs(1, 1)

进入 dfs(1, 1)

1
2
3
n - i = 5（剩下 "55255"）
4 - j = 3
条件：3 <= 5 <= 9 ✅

枚举子串 right 从 1 开始（因为 i=1）

right=1："5"
ipVal = 5 ✅
path[1] = "5"
进入 dfs(2, 2)

进入 dfs(2, 2)

1
2
3
n - i = 4（剩下 "5255"）
4 - j = 2
条件：2 <= 4 <= 6 ✅

枚举子串 right 从 2 开始

right=2："5"
ipVal = 5 ✅
path[2] = "5"
进入 dfs(3, 3)

进入 dfs(3, 3)

1
2
3
n - i = 3（剩下 "255"）
4 - j = 1
条件：1 <= 3 <= 3 ✅

枚举子串 right 从 3 开始

right=3："2"
ipVal = 2 ✅
path[3] = "2"
进入 dfs(4, 4)

进入 dfs(4, 4)

1
2
3
4
i = 4，n = 6
n - i = 2
4 - j = 0
条件：0 <= 2 <= 0 ❌ （2 > 0）

直接 return

所以 right=3 这条路失败。

回溯到 dfs(3, 3) 继续循环

right=4：子串 "25"（i=3 到 4）
ipVal = 2*10 + 5 = 25 ✅
path[3] = "25"（覆盖掉之前的 "2"）

进入 dfs(5, 4)

进入 dfs(5, 4)

1
2
3
n - i = 1
4 - j = 0
条件：0 <= 1 <= 0 ❌

失败。

right=5：子串 "255"
ipVal = 2*10 + 5 = 25 → 25*10 + 5 = 255 ✅
path[3] = "255"

进入 dfs(6, 4)

进入 dfs(6, 4)

1
2
i == n（6 == 6）
ans.add(String.join(".", path))
1
2
path` 当前内容：
`["2", "5", "5", "255"]

组成 IP：2.5.5.255 ✅

回到 dfs(2,2) 继续

此时 dfs(2,2) 里的循环 right 继续：

之前 right=2 已经试过（"5"），
现在 right=3：子串 "52"（i=2 到 3）
ipVal = 5*10 + 2 = 52 ✅
path[2] = "52"

进入 dfs(4, 3)

dfs(4, 3)

1
2
3
n - i = 2（剩下 "55"）
4 - j = 1
条件：1 <= 2 <= 3 ✅

枚举子串 right 从 4 开始

right=4："5"
ipVal = 5 ✅
path[3] = "5"
进入 dfs(5, 4) → 失败

right=5："55"
ipVal = 5*10 + 5 = 55 ✅
path[3] = "55"
进入 dfs(6, 4) → 成功

添加 IP：["2", "5", "52", "55"] → 2.5.52.55 ✅

继续回溯到 dfs(2,2)，right=4
子串 "525"（i=2 到 4）
ipVal = 5*10 + 2 = 52 → 52*10 + 5 = 525
525 > 255 ❌ break

后续过程省略…

78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

1
2
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

1
2
输入：nums = [0]
输出：[[],[0]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 改代码只需要在 77.组合 的基础上稍加修改即可
class Solution {
    private List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        getCombine(0, n, nums, new ArrayList<>());
        return ans;
    }

    public void getCombine(int start, int n, int[] nums, List<Integer> list) {
        // 记录解
        ans.add(new ArrayList<>(list));
        // 遍历所有选择
        for (int i = start; i < n; i++) {
            // 尝试：做出选择，更新状态
            list.add(nums[i]);
            // 进行下一轮选择
            getCombine(i + 1, n, nums, list);
            // 回退：撤销选择，恢复到之前的状态
            list.remove(list.size() - 1);
        }
    }
}

90. 子集 II

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

1
2
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

1
2
输入：nums = [0]
输出：[[],[0]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    private List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        getCombine(0, n, nums, new ArrayList<>());
        return ans;
    }

    public void getCombine(int start, int n, int[] nums, List<Integer> list) {
        // 记录解
        ans.add(new ArrayList<>(list));
        // 遍历所有选择
        for (int i = start; i < n; i++) {
            // 剪枝,消除掉重复元素
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            // 尝试：做出选择，更新状态
            list.add(nums[i]);
            // 进行下一轮选择
            getCombine(i + 1, n, nums, list);
            // 回退：撤销选择，恢复到之前的状态
            list.remove(list.size() - 1);
        }
    }

}

注意

这里的剪枝条件 i > start确保了只有当具有相同值的数不处于同一层，才能纳入选择：如示例1，在start为0时，比较后两个2的值，只取其中一个2，而当start为1时，已经取得了[1,2]，这时可以将最后一个2纳入其中。

491. 非递减子序列

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例 1：

1
2
输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例 2：

1
2
输入：nums = [4,4,3,2,1]
输出：[[4,4]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    private List<List<Integer>> ans = new ArrayList<>();
    
    public List<List<Integer>> findSubsequences(int[] nums) {
        dfs(0, nums, new ArrayList<>());
        return ans;
    }
    
    private void dfs(int start, int[] nums, List<Integer> path) {
        if (path.size() >= 2) {
            ans.add(new ArrayList<>(path));
        }
        
        Set<Integer> used = new HashSet<>(); // 本层去重
        for (int i = start; i < nums.length; i++) {
            // 非递减条件
            if (!path.isEmpty() && nums[i] < path.get(path.size() - 1)) {
                continue;
            }
            // 同一层重复元素剪枝
            if (used.contains(nums[i])) {
                continue;
            }
            used.add(nums[i]);
            path.add(nums[i]);
            dfs(i + 1, nums, path);
            path.remove(path.size() - 1);
        }
    }
}

注意

涉及到的剪枝条件过多，需要分成两部分

46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

1
2
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

1
2
输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

1
2
输入：nums = [1]
输出：[[1]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        int n = nums.length;
        List<Integer> path = Arrays.asList(new Integer[n]); // 所有排列的长度都是一样的 n
        boolean[] onPath = new boolean[n];
        List<List<Integer>> ans = new ArrayList<>();

        dfs(0, nums, ans, path, onPath);
        return ans;
    }

    // 枚举 path[i] 填 nums 的哪个数
    private void dfs(int i, int[] nums, List<List<Integer>> ans, List<Integer> path, boolean[] onPath) {
        if (i == nums.length) {
            ans.add(new ArrayList<>(path));
            return;
        }

        for (int j = 0; j < nums.length; j++) {
            if (!onPath[j]) {
                path.set(i, nums[j]); // 从没有选的数字中选一个
                onPath[j] = true; // 已选上
                dfs(i + 1, nums, ans, path, onPath);
                onPath[j] = false; // 恢复现场
                // 注意 path 无需恢复现场，因为排列长度固定，直接覆盖就行
            }
        }
    }
}

步骤图解

1. 初始状态

  • nums = [1, 2, 3]
  • n = 3
  • path = [_, _, _] （长度为 3，初始占位）
  • onPath = [false, false, false]
  • ans = []

调用 dfs(0, ...)。

2. 递归树展开

2.1 第一层：i = 0

循环 j = 0,1,2，尝试填充 path[0]。

j = 0

  • path[0] = 1, onPath[0] = true
  • 调用 dfs(1, ...)

2.2 第二层：i = 1

当前 path: [1, _, _]
onPath: [T, F, F]

循环 j = 0,1,2：跳过 j=0（已用）。

j = 1

  • path[1] = 2, onPath[1] = true
  • 调用 dfs(2, ...)

2.3 第三层：i = 2

当前 path: [1, 2, _]
onPath: [T, T, F]

循环 j = 0,1,2：跳过 j=0,1。

j = 2

  • path[2] = 3, onPath[2] = true
  • 调用 dfs(3, ...)

3.1 第四层：i = 3（叶子）

  • i == n（3），ans.add([1,2,3])
  • 返回上一层

3.2 回到第三层：i = 2，j = 2 执行完成

  • 恢复现场：onPath[2] = false
  • 循环结束，返回上一层

2.4 回到第二层：i = 1，j = 1 执行完成

恢复现场：onPath[1] = false
继续循环 j=2。

j = 2（在 i=1 层）

  • path[1] = 3, onPath[2] = true
  • 调用 dfs(2, ...)

第三层：i = 2

当前 path: [1, 3, _]
onPath: [T, F, T]

循环 j = 0,1,2：跳过 j=0,2。

j = 1

  • path[2] = 2, onPath[1] = true
  • 调用 dfs(3, ...)

叶子

i=3 → ans 添加 [1, 3, 2]

返回上一级，恢复 onPath[1] = false。

i=2 层循环结束，返回上一层。

回到第二层 i=1，j=2 结束

恢复 onPath[2] = false。

第二层循环结束，返回第一层。

2.5 回到第一层 i=0，j=0 结束

恢复 onPath[0] = false。

2.6 第一层，i=0，j=1

1
path[0] = 2`, `onPath[1] = true
  • 继续递归，过程类似，生成以 2 开头的排列 [2, 1, 3] 和 [2, 3, 1]

2.7 第一层，i=0，j=2

1
path[0] = 3`, `onPath[2] = true
  • 生成以 3 开头的排列 [3, 1, 2] 和 [3, 2, 1]

3. 最终 ans 收集的排列顺序

(按递归深度优先遍历生成顺序)：

  1. [1, 2, 3]
  2. [1, 3, 2]
  3. [2, 1, 3]
  4. [2, 3, 1]
  5. [3, 1, 2]
  6. [3, 2, 1]

47. 全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

1
2
3
4
5
输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

1
2
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);

        int n = nums.length;
        List<Integer> path = Arrays.asList(new Integer[n]); // 所有排列的长度都是 n
        boolean[] onPath = new boolean[n]; // onPath[j] 表示 nums[j] 是否已经填入排列
        List<List<Integer>> ans = new ArrayList<>();

        dfs(0, nums, path, onPath, ans);
        return ans;
    }

    // i 表示当前要填排列的第几个数
    private void dfs(int i, int[] nums, List<Integer> path, boolean[] onPath, List<List<Integer>> ans) {
        if (i == nums.length) { // 填完了
            ans.add(new ArrayList<>(path));
            return;
        }

        // 枚举 nums[j] 填入 path[i]
        for (int j = 0; j < nums.length; j++) {
            // 如果 nums[j] 已填入排列，continue
            // 如果 nums[j] 和前一个数 nums[j-1] 相等，且 nums[j-1] 没填入排列，continue
            if (onPath[j] // 情况1：当前数字已经在排列中
                ||
                (j > 0 && nums[j] == nums[j - 1] && !onPath[j - 1]) // 情况2：重复数字且前一个未被使用
               ) {
                continue;
            }
            path.set(i, nums[j]); // 填入排列
            onPath[j] = true; // nums[j] 已填入排列（注意标记的是下标，不是值）
            dfs(i + 1, nums, path, onPath, ans); // 填排列的下一个数
            onPath[j] = false; // 恢复现场
            // 注意 path 无需恢复现场，因为排列长度固定，直接覆盖 path[i] 就行
        }
    }
}

注意

  1. 去重问题需要排列。
  2. 该题的复杂度已超过了临场理解的范畴，需要结合 90. 子集 II 和 46. 全排列 来理解；实战中不要求做出。