代码随想录之回溯算法

回溯算法

组合——以本题为例理解回溯思想和剪枝操作

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2
输出：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

画图便于理解回溯，每次记录路径以便于回溯。剪枝剪掉长度不到k的无效路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    // 记录每次的路径
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> combine(int n, int k) {
        backtracking(n, k, 1);
        return res;
    }

    public void backtracking(int n, int k, int startIndex){
        if(path.size() == k){
            res.add(new ArrayList<>(path));
            return;
        }

        // 剪枝操作，避免无效遍历，因为这些剪枝的长度到不了k
        for(int i = startIndex; i <= n - (k - path.size()) + 1; i++){
            path.add(i);
            backtracking(n, k, i + 1);
            path.removeLast(); // 回溯
        }
    }
}

组合总和——前置剪枝与后置剪枝

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

前置剪枝更复杂，但是效率更高。

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
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        // backtracking1(k, n, 0, 1);
        backtracking2(k, n, 0, 1);
        return res;
    }

    // 前置剪枝，剪掉永远不会到达path.size() == k的部分
    private void backtracking1(int k, int n, int sum, int startIndex){
        if(sum > n) return;

        if(path.size() == k){
            if(sum == n) res.add(new ArrayList<>(path));
            return;
        }

        for(int i = startIndex; i <= 9 - (k - path.size()) + 1; i++){
            path.add(i);
            sum += i;
            backtracking1(k, n, sum, i + 1);
            sum -= i;
            path.removeLast();
        }
    }

    // 后置剪枝，剪掉path.size() > k的部分，及时止损
    private void backtracking2(int k, int n, int sum, int startIndex){
        if(sum > n) return;

        if(path.size() > k) return;

        if(sum == n && path.size() == k){
            res.add(new ArrayList<>(path));
            return;
        }

        for(int i = startIndex; i <= 9; i++){
            path.add(i);
            sum += i;
            backtracking2(k, n, sum, i + 1);
            sum -= i;
            path.removeLast();
        }
    }
}

电话号码的字母组合——理解回溯的层数

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

用数组记录按键与字母的关系，理解回溯的层数与path处理的关系，画图理解。

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 {
    List<String> res = new ArrayList<>();
    StringBuilder path = new StringBuilder();
    String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    public List<String> letterCombinations(String digits) {
        if(digits == null || digits.length() == 0){
            return res;
        }
        backtracking(digits, 0);
        return res;
    }

    public void backtracking(String digits, int num){
        // num记录digits的第几位
        if(num == digits.length()){
            res.add(path.toString());
            return;
        }

        String str = numString[digits.charAt(num) - '0'];
        for(int i = 0; i < str.length(); i++){
            // path的每一位表示的是第几层，在这里表示第几位
            path.append(str.charAt(i));
            backtracking(digits, num + 1);
            path.deleteCharAt(path.length() - 1);
        }
    }
}

分割回文串

给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
示例 1：
输入：s = “aab”
输出：[[“a”,”a”,”b”],[“aa”,”b”]]
示例 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
35
36
37
class Solution {
    List<List<String>> res = new ArrayList<>();
    List<String> path = new ArrayList<>();

    public List<List<String>> partition(String s) {
        backtracking(s, 0);
        return res;
    }

    private void backtracking(String s, int startIndex){
        if(startIndex == s.length()){
            res.add(new ArrayList<>(path));
            return;
        }

        StringBuilder sb = new StringBuilder();

        for(int i = startIndex; i < s.length(); i++){
            sb.append(s.charAt(i)); // 寻找回文前缀
            if(check(sb)){
                path.add(sb.toString());
                backtracking(s, i + 1);
                path.removeLast();
            }
        }
    }

    // 这里还可以用动态规划优化
    private boolean check(StringBuilder sb){
        for(int i = 0; i < sb.length() / 2; i++){
            if(sb.charAt(i) != sb.charAt(sb.length() - i - 1)){
                return false;
            }
        }
        return true;
    }
}

复原 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
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 {
    List<String> res = new ArrayList<>();
    StringBuilder sb = new StringBuilder();

    public List<String> restoreIpAddresses(String s) {
        backtracking(s, 0, 0);
        return res;
    }

    private void backtracking(String s, int startIndex, int dotNum){
        if(startIndex == s.length() && dotNum == 4){
            res.add(sb.toString());
            return;
        }

        // 非法
        if(startIndex == s.length() || dotNum == 4){
            return;
        }

        // 剪枝方法：整数介于[0,255]，因此最多三位
        for(int i = startIndex; i < s.length() && i - startIndex < 3 && Integer.parseInt(s.substring(startIndex, i + 1)) >= 0 && Integer.parseInt(s.substring(startIndex, i + 1)) <= 255; i++){
            // 非零开头
            if(i + 1 - startIndex > 1 && s.charAt(startIndex) == '0'){
                return;
            }
            sb.append(s.substring(startIndex, i + 1));
            // 加dot
            if(dotNum < 3) sb.append(".");
            backtracking(s, i + 1, dotNum + 1);
            sb.delete(startIndex + dotNum, i + dotNum + 2);
        }
    }
}

子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

不同于组合和切割问题，树上的每个节点都要压入结果集。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

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

    private void backtracking(int[] nums, int startIndex){
        res.add(new ArrayList<>(path)); // 树上的每个节点都要放上去
        if(startIndex >= nums.length){
            return;
        }
        for(int i = startIndex; i < nums.length; i++){
            path.add(nums[i]);
            backtracking(nums, i + 1);
            path.removeLast();
        }
    }
}

非递减子序列——利用哈希表去重

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

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 {
    // 由于要找递增子序列，故不能排序，使用哈希表
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

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

    private void backtracking(int[] nums, int startIndex){
        if(path.size() >= 2){
            res.add(new ArrayList<>(path));
        }
        HashSet<Integer> hs = new HashSet<>();
        for(int i = startIndex; i < nums.length; i++){
            // 保证递增和去重
            if((!path.isEmpty() && path.get(path.size() - 1) > nums[i]) || hs.contains(nums[i])){
                continue;
            }
            hs.add(nums[i]);
            path.add(nums[i]);
            backtracking(nums, i + 1);
            path.removeLast();
        }
    }
}

全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：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
class Solution {
    // 使用完全树不剪枝，因此要注意去重
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

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

    
    // 完全树用不到startIndex
    private void backtracking(int[] nums){
        if(path.size() == nums.length){
            res.add(new ArrayList<>(path));
            return;
        }

        for(int i = 0; i < nums.length; i++){
            if(path.contains(nums[i])){
                // 去重
                continue;
            }
            path.add(nums[i]);
            backtracking(nums);
            path.removeLast();
        }
    }
}

全排列 II——去重的思想

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

理解这里怎么去重的。

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 {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        // used用于记录index的数字用过没有
        boolean[] used = new boolean[nums.length];
        // 默认为false
        Arrays.fill(used, false);
        Arrays.sort(nums);
        backtracking(nums, used);
        return res;
    }

    private void backtracking(int[] nums, boolean[] used){
        if(path.size() == nums.length){
            res.add(new ArrayList<>(path));
            return;
        }

        for(int i = 0; i < nums.length; i++){
            // used记录path用过没有，用过可以去用相等但没用过的数字；但没用过的话，说明在该层中用过相等的数字，会重复，不能使用
            if(i > 0 && nums[i - 1] == nums[i] && used[i - 1] == false){
                continue;
            }

            // 用used去重的方法，这里不能用path.contains()的方法，因为有相等数字
            if(used[i] == false){
                used[i] = true;
                path.add(nums[i]);
                backtracking(nums, used);
                path.removeLast();
                used[i] = false;
            }
        }
    }
}

N皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

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
class Solution {
    List<List<String>> res = new ArrayList<>();
    boolean[] usedCol, used45, used135;

    public List<List<String>> solveNQueens(int n) {
        usedCol = new boolean[n]; // 保证不在同一列
        used45 = new boolean[2 * n + 1]; // 保证不在45度斜线内
        used135 = new boolean[2 * n + 1]; // 保证不在135度斜线内
        // 收集结果
        int[] board = new int[n];
        backtracking(board, n, 0);
        return res;
    }

    // 使用行来回溯
    private void backtracking(int[] board, int n, int row){
        if(row == n){
            // 解释结果
            List<String> path = new ArrayList<>();
            for(int i : board){
                char[] str = new char[n];
                Arrays.fill(str, '.');
                str[i] = 'Q';
                path.add(new String(str));
            }
            res.add(path);
            return;
        }

        for(int col = 0; col < n; col++){
            if(usedCol[col] || used45[row + col] || used135[n - 1 - col + row]){ // 不在同一列和同一斜线上
                continue;
            }
            board[row] = col;
            usedCol[col] = true;
            used45[row + col] = true;
            used135[n - 1 - col + row] = true;
            backtracking(board, n, row + 1);
            usedCol[col] = false;
            used45[row + col] = false;
            used135[n - 1 - col + row] = false;
        }
    }
}

解数独

编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

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
54
55
56
class Solution {
    public void solveSudoku(char[][] board) {
        backtracking(board);
    }

    // 同样是唯一解，用boolean
    private boolean backtracking(char[][] board){
        for(int i = 0; i < 9; i++){ // 遍历行
            for(int j = 0; j < 9; j++){ // 遍历列
                if(board[i][j] != '.'){
                    continue;
                }
                for(char k = '1'; k <= '9'; k++){
                    if(isValid(i, j, k, board)){
                        board[i][j] = k;
                        if(backtracking(board)){
                            return true;
                        }
                        board[i][j] = '.';
                    }
                }
                return false;
            }
        }
        return true;
    }

    private boolean isValid(int row, int column, char val, char[][] board){
        // 同行是否重复
        for(int i = 0; i < 9; i++){
            if(board[row][i] == val){
                return false;
            }
        }

        // 同列是否重复
        for(int i = 0; i < 9; i++){
            if(board[i][column] == val){
                return false;
            }
        }

        // 九宫格内是否重复
        int startRow = (row / 3) * 3;
        int startColumn = (column / 3) * 3;
        for(int i = startRow; i < startRow + 3; i++){
            for(int j = startColumn; j < startColumn + 3; j++){
                if(board[i][j] == val){
                    return false;
                }
            }
        }

        return true;
    }
}
力扣 > 代码随想录
#leetcode
代码随想录之回溯算法
http://example.com/2025/06/15/代码随想录之回溯算法/
作者
jietiDdd
发布于
2025年6月15日
许可协议