Jiaming Zhang's Blog
0%

算法-回溯

发表于 更新于

回溯相关算法题

77. 组合【基】

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

1
2
3
输入：n = 4, k = 2
输出：
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,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
31
32
33
34
35
36
37
public class TraceBack {

    public List<List<Integer>> combine(int n, int k) {
        List<Integer> path = new ArrayList<>();
        List<List<Integer>> result = new ArrayList<>();
        trace(n, k, 1, path, result);
        return result;
    }

    /**
     * 回溯过程
     * @param n 数字的范围
     * @param k 回溯树的深度
     * @param startNum 当前回溯层的开始值
     * @param path 一条回溯路径
     * @param result 所有回溯路径
     */
    private void trace(int n, int k, int startNum, List<Integer> path, List<List<Integer>> result) {
        // 减支：如果当前层不能满足k的深度要求，不向下搜索
        if (n - startNum + 1 < k) {
            return;
        }
        // 回溯到最下面一层（叶子节点）
        if (k == 0) {
            // 新创建一个list，用一个list会干扰
            result.add(new ArrayList<>(path));
            return;
        }
        // 当前层，从开始数字遍历到n，如 [3,4,5]
        for (int i = startNum; i <= n; i++) {
            path.add(i);
            // 下一层，深度-1，如i=3，下一层应为[4,5]
            trace(n, k - 1, i + 1, path, result);
            path.remove(path.size() - 1);
        }
    }
}

216. 组合总和 III

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

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

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

1
2
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,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
class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<Integer> path = new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        traceForCombinationSum3(k, n, 1, 0, path, res);
        return res;
    }

    private void traceForCombinationSum3(int k, int n, int start, int sum, List<Integer> path, List<List<Integer>> res) {
        if (sum == n && k == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        if (sum > n || k == 0) {
            return;
        }
        // 回溯过程
        for (int i = start; i <= 9; i++) {
            path.add(i);
            traceForCombinationSum3(k-1, n, i+1, sum + i, path, res);
            path.remove(path.size() - 1);
        }
    }
}

17. 电话号码的字母组合

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

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

1
2
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
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<String> letterCombinations(String digits) {
        if (digits == null || "".equals(digits)) {
            return new ArrayList<>();
        }
        char[][] telephone = {
                {},
                {},
                {'a', 'b', 'c'},
                {'d', 'e', 'f'},
                {'g', 'h', 'i'},
                {'j', 'k', 'l'},
                {'m', 'n', 'o'},
                {'p', 'q', 'r', 's'},
                {'t', 'u', 'v'},
                {'w', 'x', 'y', 'z'}
        };
        List<String> res = new ArrayList<>();
        traceForLetterCombinations(digits, 0, new StringBuilder(""), res, telephone);
        return res;
    }

    private void traceForLetterCombinations(String digits, int index, StringBuilder s,
                                            List<String> res, char[][] telephone) {
        // 回溯一条路径的结束条件：当到达最下面一层（叶子节点），终止
        if (index == digits.length()) {
            res.add(s.toString());
            return;
        }
        int number = digits.charAt(index) - '0';
        char[] chars = telephone[number];
        for (int i = 0; i < chars.length; i++) {
            s.append(chars[i]);
            traceForLetterCombinations(digits, index + 1, s, res, telephone);
            s.deleteCharAt(s.length() - 1);
        }
    }
}

39. 组合总和【难】

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

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

1
2
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,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
27
28
29
30
31
32
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        if (candidates == null || candidates.length == 0) {
            return new ArrayList<>();
        }
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        traceForCombinationSum(candidates, 0, target, 0, new ArrayList<>(), res);
        return res;
    }

    private void traceForCombinationSum(int[] candidates, int sum, int target, int start,
                                        List<Integer> arr, List<List<Integer>> res) {
        if (sum > target) {
            return;
        }
        // 终止条件
        if (sum == target) {
            res.add(new ArrayList<>(arr));
            return;
        }
        // 回溯过程
        for (int i = start; i < candidates.length; i++) {
            if (sum + candidates[i] > target) {
                break;
            }
            arr.add(candidates[i]);
            traceForCombinationSum(candidates, sum + candidates[i], target, i, arr, res);
            arr.remove(arr.size() - 1);
        }
    }
}

40. 组合总和 II

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

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

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

1
2
3
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[[1,1,6],[1,2,5],[1,7],[2,6]]
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 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if (candidates == null || candidates.length == 0) {
            return new ArrayList<>();
        }
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates);
        traceForCombinationSum2(candidates, 0, 0, target, new ArrayList<>(), res);
        return res;
    }

    private void traceForCombinationSum2(int[] candidates, int start, int sum, int target,
                                         List<Integer> path, List<List<Integer>> res) {
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }
        if (sum > target) {
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (i > start && candidates[i] == candidates[i-1]) {
                continue;
            }
            path.add(candidates[i]);
            traceForCombinationSum2(candidates, i + 1, sum + candidates[i], target, path, res);
            path.remove(path.size() - 1);
        }
    }
}

小结：组合问题都遇到了对原始数组排序，回溯过程中去重的方法，去重是只在同一层，跳过一些数值，防止组合结果重复

131. 分割回文串

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

回文串 是正着读和反着读都一样的字符串

1
2
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
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
class Solution {

    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        if (s == null || s.isEmpty()) {
            return res;
        }
        trace(s, 0, new ArrayList<>(), res);
        return res;
    }

    private void trace(String s, int start, List<String> palindrome, List<List<String>> res) {
        if (s.length() == start) {
            res.add(new ArrayList<>(palindrome));
            return;
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = start; i < s.length(); i++) {
            stringBuilder.append(s.charAt(i));
            if (isPalindrome(stringBuilder.toString())) {
                palindrome.add(stringBuilder.toString());
                trace(s, i + 1, palindrome, res);
                palindrome.remove(palindrome.size() - 1);
            }
        }

    }

    /**
     * 判断回文串
     * @param s
     * @return
     */
    private boolean isPalindrome(String s) {
        if (s == null || s.isEmpty()) {
            return false;
        }
        int len = s.length();
        for (int i = 0; i < len / 2; i++) {
            if (s.charAt(i) != s.charAt(len - i - 1)) {
                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
2
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
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
class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<List<String>> res = new ArrayList<>();
        List<String> ipList = new ArrayList<>();
        if (s == null || s.isEmpty()) {
            return ipList;
        }
        traceForRestoreAIpAddresses(s, 0, 0, new ArrayList<>(), res);
        for (int i = 0; i < res.size(); i++) {
            StringBuilder stringBuilder = new StringBuilder();
            for (int j = 0; j < res.get(i).size(); j++) {
                stringBuilder.append(res.get(i).get(j)).append(".");
            }
            stringBuilder.deleteCharAt(stringBuilder.length() - 1);
            ipList.add(stringBuilder.toString());
        }
        return ipList;
    }

    private void traceForRestoreAIpAddresses(String s, int start, int ipNum,
                                             List<String> ip, List<List<String>> res) {
        if (ipNum == 4 && start != s.length()) {
            return;
        }
        if (ipNum == 4) {
            res.add(new ArrayList<>(ip));
            return;
        }
        StringBuilder strBuilder = new StringBuilder();
        for (int i = start; i < Math.min(start + 3, s.length()); i++) {
            strBuilder.append(s.charAt(i));
            if (availableIP(strBuilder.toString())) {
                ip.add(strBuilder.toString());
                traceForRestoreAIpAddresses(s, i + 1, ipNum + 1, ip, res);
                ip.remove(ip.size() - 1);
            }
        }
    }

    /**
     * 判断分割的字符串是否为有效IP
     * @param s
     * @return
     */
    private boolean availableIP(String s) {
        if (s.length() > 1 && s.charAt(0) == '0') {
            return false;
        }
        int value = Integer.parseInt(s);
        if (value < 0 || value > 255) {
            return false;
        }
        return true;
    }
}

78. 子集

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

1
2
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        trace(nums, 0, true, new ArrayList<>(), res);
        return res;
    }

    private void trace(int[] nums, int start, boolean next, List<Integer> subSet, List<List<Integer>> res) {
        res.add(new ArrayList<>(subSet));
        for (int i = start; i < nums.length; i++) {
            subSet.add(nums[i]);
            trace(nums, i+1, true, subSet, res);
            subSet.remove(subSet.size() - 1);
        }
    }
}

90. 子集 II

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

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

1
2
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        traceForSubsetsWithDup(nums, 0, true, new ArrayList<>(), res);
        return res;
    }

    private void traceForSubsetsWithDup(int[] nums, int start, boolean next,
                                        List<Integer> subSet, List<List<Integer>> res) {
        res.add(new ArrayList<>(subSet));
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i-1]) {
                continue;
            }
            subSet.add(nums[i]);
            traceForSubsetsWithDup(nums, i+1, true, subSet, res);
            subSet.remove(subSet.size() - 1);
        }
    }
}

注：重点在于如果去重，与40. 组合总和 II思路相同

491. 递增子序列【难】

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

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

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]]
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<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        traceForFindSubSequences(nums, 0, false, new ArrayList<>(), res);
        return res;
    }

    private void traceForFindSubSequences(int[] nums, int start, boolean finish,
                                          List<Integer> subsequence, List<List<Integer>> res) {
        if (finish) {
            res.add(new ArrayList<>(subsequence));
            return;
        }
        if (subsequence.size() > 1) {
            traceForFindSubSequences(nums, start, true, subsequence, res);
        }
        Set<Integer> set = new HashSet<>();
        for (int i = start; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                continue;
            }
            if (start - 1 >= 0 && nums[i] < nums[start - 1]) {
                continue;
            }
            set.add(nums[i]);
            subsequence.add(nums[i]);
            traceForFindSubSequences(nums, i+1, false, subsequence, res);
            subsequence.remove(subsequence.size() - 1);
        }
    }
}

去重条件为：本行遍历中出现重复的数字，就会导致最后结果重复

思考：为什么40. 组合总和 II与90. 子集 II可以直接通过与前一个元素比较去重？

原因：那两道题可以先对数组排序，让相等的数字连续出现，而本题要保证先对顺序，不能排序，故需要用set去重

46. 全排列

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

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
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        traceForPermute(nums, new ArrayList<>(), res);
        return res;
    }

    private void traceForPermute(int[] nums, List<Integer> permute, List<List<Integer>> res) {
        if (permute.size() == nums.length) {
            res.add(new ArrayList<>(permute));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (permute.contains(nums[i])) {
                continue;
            }
            permute.add(nums[i]);
            traceForPermute(nums, permute, res);
            permute.remove(permute.size() - 1);
        }
    }
}

47. 全排列 II

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

1
2
3
输入：nums = [1,1,2]
输出：
[[1,1,2],[1,2,1],[2,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
30
31
32
33
34
35
36
class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        Arrays.sort(nums);
        traceForPermuteUnique(nums, new ArrayList<>(), new ArrayList<>(), res);
        return res;
    }

    private void traceForPermuteUnique(int[] nums, List<Integer> numIndexList, List<Integer> permuteUnique, List<List<Integer>> res) {
        if (permuteUnique.size() == nums.length) {
            res.add(new ArrayList<>(permuteUnique));
            return;
        }
        Integer preNum = null;
        for (int i = 0; i < nums.length; i++) {
            if (numIndexList.contains(i)) {
                continue;
            }
            if (preNum == null) {
                preNum = nums[i];
            } else if (nums[i] == preNum) {
                continue;
            } else {
                preNum = nums[i];
            }
            permuteUnique.add(nums[i]);
            numIndexList.add(i);
            traceForPermuteUnique(nums, numIndexList, permuteUnique, res);
            permuteUnique.remove(permuteUnique.size() - 1);
            numIndexList.remove(numIndexList.size() - 1);
        }
    }
}

Hard问题待做

332. 重新安排行程

51. N 皇后

37. 解数独

总结

回溯问题存在明显的解题规律：

  1. 画回溯树
  2. 创建存放所有路径的二维数组（一般情况）
  3. 写回溯函数
    1. 确定回溯结束条件，当一条路径结束，将该路径新创建一份，放到二维数组中
    2. 对当前层遍历，减枝（去重：一般的，如果要求路径不能重复，则当前层一些重复值不能向下遍历）
    3. 向下一层遍历，减枝（去重：与之前路径中不能重复，一般用起始位置，或直接在路径中判断是否存在）
    4. 向上一层回溯（路径减去最后一个元素）
  4. 返回带有所有路径的二维数组