风在路上
zdk
2022-03-18
目录

回溯

Table of Contents generated with DocToc (opens new window)

# 概要及框架

解决一个回溯问题，实际上就是一个决策树的遍历过程。你只需要思考 3 个问题：

1、路径：也就是已经做出的选择。

2、选择列表：也就是你当前可以做的选择。

3、结束条件：也就是到达决策树底层，无法再做选择的条件。

框架

result = []
def backtrace(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrace(路径, 选择列表)
        撤销选择
1
2
3
4
5
6
7
8
9
10

其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」

我们只要在递归之前做出选择，在递归之后撤销刚才的选择，就能正确得到每个节点的选择列表和路径。

回溯算法就是个多叉树的遍历问题，关键就是在前序遍历和后序遍历的位置做一些操作，算法框架如下：

写 backtrace 函数时，需要维护走过的「路径」和当前可以做的「选择列表」，当触发「结束条件」时，将「路径」记入结果集。

其实想想看，回溯算法和动态规划是不是有点像呢？我们在动态规划系列文章中多次强调，动态规划的三个需要明确的点就是「状态」「选择」和「base case」，是不是就对应着走过的「路径」，当前的「选择列表」和「结束条件」？

某种程度上说，动态规划的暴力求解阶段就是回溯算法。只是有的问题具有重叠子问题性质，可以用 dp table 或者备忘录优化，将递归树大幅剪枝，这就变成了动态规划。而今天的两个问题，都没有重叠子问题，也就是回溯算法问题了，复杂度非常高是不可避免的。

# 排列/组合/子集问题

# 1.(medium)全排列

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

示例 1：

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

思路：

回溯：

我们使用一个boolean数组flag来保存当前的所有选择的状态，为true证明已被选则，不可被选。

使用LinkedList来记录每次结果，当它的size到达nums的length的时候，证明产生一个排列，将其加入到res中

注：res.add(new LinkedList<>(path));老问题了

  1. 在回溯方法中，如果当前的path长度等于nums长度，证明产生一个排列
  2. 然后对所有的可选选择进行选择，将其加入到path中,将选择标志flag[i]记为true
  3. 然后执行递归
  4. 递归完成后，将path中的最后一个移出，然后将选择标志flag[i]记为false

2、4步即体现了在递归调用之前「做选择」，在递归调用之后「撤销选择」

代码：

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        boolean[] flag = new boolean[nums.length];
        backtrace(new LinkedList<>(),nums,flag);
        return res;
    }

    public void backtrace(LinkedList<Integer> path,int[] nums,boolean[] flag){
        if(path.size() == nums.length){
            res.add(new LinkedList<>(path));
            return;
        }
        //遍历所有选择
        for(int i=0;i<nums.length;i++){
            //已选择的 不再选择
            if(flag[i]){
                continue;
            }
            //选择
            path.add(nums[i]);
            //标记置为已选择
            flag[i] = true;
            //递归
            backtrace(path,nums,flag);
            //撤销选择
            path.removeLast();
            //标记置为未选择
            flag[i] = false;
        }
    }
}
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

# 2.(medium)全排列2

题目与上题类似，只是数组现在包含重复数字，且要求返回的是所有不重复的全排列

思路：

大题思路与上题一致，需要解决的问题：

如何筛选重复的排列，即减枝

要解决重复问题，我们只要设定一个规则，保证在填第i个数的时候重复数字只会被填入一次即可。而在本题解中，我们选择对原数组排序，保证相同的数字都相邻，然后每次填入的数一定是这个数所在重复数集合中「从左往右第一个未被填过的数字」，即如下的判断条件：

if (i > 0 && nums[i] == nums[i - 1] && !flag[i - 1]) {
    continue;
}
1
2
3

这个判断条件保证了对于重复数的集合，一定是从左往右逐个填入的。

假设我们有 33 个重复数排完序后相邻，那么我们一定保证每次都是拿从左往右第一个未被填过的数字，即整个数组的状态其实是保证了 [未填入，未填入，未填入] 到 [填入，未填入，未填入]，再到 [填入，填入，未填入]，最后到 [填入，填入，填入] 的过程的，因此可以达到去重的目标。

代码：

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        boolean[] flag = new boolean[nums.length];
        backtrace(new LinkedList<>(),nums,flag);
        return res;
    }

    public void backtrace(LinkedList<Integer> path,int[] nums,boolean[] flag){
        if(path.size() == nums.length){
            res.add(new LinkedList<>(path));
            return;
        }
        //遍历所有选择
        for(int i=0;i<nums.length;i++){
            //已选择的 不再选择
            if(flag[i]){
                continue;
            }
            //如果前面的相邻相等元素没有用过，则跳过
            if(i>0&&nums[i]==nums[i-1]&&!flag[i-1]){
                continue;
            }
            //选择
            path.add(nums[i]);
            //标记置为已选择
            flag[i] = true;
            //递归
            backtrace(path,nums,flag);
            //撤销选择
            path.removeLast();
            //标记置为未选择
            flag[i] = false;
        }
    }
}
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

# 3.(medium)划分为k个相等的子集

给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

示例 1：

输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4 输出： True 说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。 示例 2:

输入: nums = [1,2,3,4], k = 3 输出: false

提示：

1 <= k <= len(nums) <= 16 0 < nums[i] < 10000 每个元素的频率在 [1,4] 范围内

思路：

将每个子集看作是一个桶，有多少个子集就有多少个桶，然后遍历nums，向桶中添加元素

  • 如果循环完nums都无法装满当前的桶，证明无法分成k个总和相等的非空子集，返回false
  • 循环时做减枝
    • 如果当前的数字已被使用，跳过
    • 如果sum+nums[i]>target即当前桶装不下，跳过
  • 然后将nums[i]装入桶，继续递归第i+1个数字是否能装入当前桶
  • 如果当前桶装满了，递归装下一个 backtrace(k-1,0,target,0,nums,flag);
  • 直到所有桶都被装满 返回true

递归函数：

public boolean backtrace(int k,int sum,int target,int start,int[] nums,boolean[] flag)
1

k表示桶个数，sum表示当前桶的值，target表示桶装满的值，start表示从数组的哪个位置开始选择数字装入桶，flag记录数字是否已被使用

代码：

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = Arrays.stream(nums).sum();
        if(sum%k!=0){
            return false;
        }
        //每个子集的和
        int target = sum/k;
        boolean[] flag = new boolean[nums.length];
        return backtrace(k,0,target,0,nums,flag);
    }

    public boolean backtrace(int k,int sum,int target,int start,int[] nums,boolean[] flag){
        //所有桶被装满了 返回true
        if(k == 0){
            return true;
        }
        //这个桶装满了 装下一个
        if(sum == target){
            return backtrace(k-1,0,target,0,nums,flag);
        }
        for(int i=start;i<nums.length;i++){
            //数字已被使用 跳过
            if(flag[i]){
                continue;
            }
            //当前桶装不下 跳过
            if(sum+nums[i]>target){
                continue;
            }
            //选择 将nums[i]装入当前桶
            sum+=nums[i];
            flag[i] = true;
            //递归穷举下一个数字(第i+1个数字)是否能装入当前桶
            if(backtrace(k,sum,target,i+1,nums,flag)){
                return true; 
            }
            //撤销
            sum-=nums[i];
            flag[i] = false;
        }
        //穷举所有数字都无法装满当前桶
        return false;
    }
}
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

# 4.(medium)所有子集

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

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

示例 1：

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

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

提示：

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • nums 中的所有元素 互不相同

思路：

使用回溯框架，但与排列不同，不需要标记元素是否已使用，题目要求解集不能包含重复的子集，而又因为nums中的元素都是不同的，所以我们只需要保证循环选择时，每次递归都向前选择即可：backtrace(subset,nums,i+1);

代码：

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        backtrace(new LinkedList<Integer>(),nums,0);
        return res;
    }

    public void backtrace(LinkedList<Integer> subset,int[] nums,int start){
        res.add(new LinkedList<>(subset));
        for(int i=start;i<nums.length;i++){
            //选择
            subset.add(nums[i]);
            backtrace(subset,nums,i+1);
            //撤销
            subset.removeLast();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 5.(medium)子集2

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

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

示例 1：

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

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

提示：

1 <= nums.length <= 10 -10 <= nums[i] <= 10

思路：

题目与上题有些许不同，nums中可能包含重复元素，且返回的解集中不能包含重复的子集。

上题是nums中没有重复数字，所以数字的相对位置是固定的；现在有重复数字，当出现重复数字的时候，它们的相对位置就不确定了，所以会产生重复的子集，要保证相对位置不变，所以我们需要固定相同元素的相对位置，像全排列2一样，对nums先排序即可，然后进行类似的剪枝

if (i > 0 && nums[i] == nums[i - 1]) {
    continue;
}
1
2
3

代码1：使用set过滤重复的 使用toString效率低

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    Set<String> set = new HashSet<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        backtrace(new LinkedList<Integer>(),nums,0);
        return res;
    }

    public void backtrace(LinkedList<Integer> subset,int[] nums,int start){
        if(set.add(subset.toString())){
            res.add(new LinkedList<>(subset));
        }
        for(int i=start;i<nums.length;i++){
            //选择
            subset.add(nums[i]);
            backtrace(subset,nums,i+1);
            //撤销
            subset.removeLast();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

代码2：根据相对位置剪枝，此种方法效率更高，因为转成数组也耗时

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        backtrace(new LinkedList<Integer>(),nums,0);
        return res;
    }

    public void backtrace(LinkedList<Integer> subset,int[] nums,int start){
        res.add(new LinkedList<>(subset));
        for(int i=start;i<nums.length;i++){
            //如果当前元素和它前一个是一样的 就不用再选了
            if(i>start&&nums[i]==nums[i-1]){
                continue;
            }
            //选择
            subset.add(nums[i]);
            backtrace(subset,nums,i+1);
            //撤销
            subset.removeLast();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 6.(medium)子集

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

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

示例 1：

输入：n = 4, k = 2 输出： [[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]] 示例 2：

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

提示：

1 <= n <= 20 1 <= k <= n

思路：

遍历到第k个元素，即有了一个子集，加入到res

每次递归时，用start参数控制树枝的遍历(只往前遍历)，避免产生重复的子集

代码：

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        backtrace(new LinkedList<Integer>(),n,k,1);
        return res;
    }

    public void backtrace(LinkedList<Integer> path,int n,int k,int start){
        if(path.size() == k){
            res.add(new LinkedList<>(path));
            return;
        }
        for(int i=start;i<=n;i++){
            path.add(i);
            backtrace(path,n,k,i+1);
            path.removeLast();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 7.(medium)组合总数

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

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

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

示例 1：

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

输入: candidates = [2,3,5], target = 8 输出: [[2,2,2,2],[2,3,3],[3,5]] 示例 3：

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

提示：

1 <= candidates.length <= 30 1 <= candidates[i] <= 200 candidate 中的每个元素都 互不相同 1 <= target <= 500

思路：

题意相当于求将nums划分为最大数量的和为target的不同子集(不同的定义是：至少一个数字的被选数量不同)

并且，题目中，同一个数字可以无限制重复被选取，不是只能选一次，只能选一次时我们的应对是，每次递归从i+1开始，而可以重复时，再次从i开始即可。

当然 也存在当当前位置的candidates[i]加上bucket大于target就剪枝的情况

代码：

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backtrace(new LinkedList<Integer>(),candidates,0,target,0);
        return res;
    }

    public void backtrace(LinkedList<Integer> path,int[] candidates,int bucket,int target,int start){
        if(bucket == target){
            res.add(new LinkedList<>(path));
            return;
        }
        for(int i=start;i<candidates.length;i++){
            if(bucket+candidates[i]>target){
                continue;
            }
            bucket+=candidates[i];
            path.add(candidates[i]);
            backtrace(path,candidates,bucket,target,i);
            path.removeLast();
            bucket-=candidates[i];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 8.(medium)组合总和2

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

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

示例 1:

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

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

思路：

题意是数字不能重复选，解集也不包含重复组合。

  1. 数字不重复选：利用boolean[]的flag数组标记当前第i的数字是否被使用过即可解决
  2. 每个数字在每个组合中只能用一次：我们利用每次递归从i+1开始即可解决
  3. 解集不包含重复组合。要知道造成重复组合的原因，是因为相同数字的相对位置不同而在循环中被视为了不同的组合，所以我们先对candidates 数组进行排序，可以将相同数字排在一起，它们的相对位置就固定了，那么在循环中我们只需要判断，如果当前数字还没有被选过，但是当前数字和它前一个数字又是相等的，证明前一个已经选过了，再选当前的candidates[i]的话就会产生重复组合，所以这种情况直接continue

然后就是这种求子集、组合的和为target的问题的常规剪枝：if(bucket+candidates[i]>target) continue;

代码：

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        boolean[] flag = new boolean[candidates.length];
        backtrace(new LinkedList<>(),candidates,flag,0,target,0);
        return res;
    }

    public void backtrace(LinkedList<Integer> path,int[] candidates,boolean[] flag,int bucket,int target,int start){
        if(bucket == target){
            res.add(new LinkedList<>(path));
            return;
        }
        for(int i=start;i<candidates.length;i++){
            if(flag[i]){
                continue;
            }
            if(i>start&&candidates[i]==candidates[i-1]&&!flag[i]){
                continue;
            }
            if(bucket+candidates[i]>target){
                continue;
            }
            path.add(candidates[i]);
            bucket+=candidates[i];
            flag[i] = true;
            backtrace(path,candidates,flag,bucket,target,i+1);
            path.removeLast();
            flag[i] = false;
            bucket-=candidates[i];
        }
    }
}
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

# 9.(medium)组合总数3

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

只使用数字1到9 每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:

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

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

输入: k = 4, n = 1 输出: [] 解释: 不存在有效的组合。 在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

思路：

  1. 每个数字最多使用一次：flag标记
  2. 因为数字不重复，且只能用一次，不用考虑相对位置的问题
  3. 不包含相同组合：每次递归从i+1开始
  4. 因为同时要求的组合的元素个数为k个，且和为n，所以bucket==n、path.size()==k同时满足才添加到res中

代码：

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        boolean[] flag = new boolean[10];
        backtrace(new LinkedList<>(),k,n,0,1,flag);
        return res;
    }
    
    public void backtrace(LinkedList<Integer> path,int k,int n,int bucket,int start,boolean[] flag){
        if(bucket==n&&path.size()==k){
            res.add(new LinkedList<>(path));
            return;
        }
        for(int i=start;i<=9;i++){
            if(flag[i]){
                continue;
            }
            if(bucket+i>n){
                continue;
            }
            path.add(i);
            flag[i] = true;
            bucket+=i;
            backtrace(path,k,n,bucket,i+1,flag);
            path.removeLast();
            flag[i] = false;
            bucket-=i;
        }
    }
}
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

# 10.(medium)字符串的排列

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:

输入：s = "abc" 输出：["abc","acb","bac","bca","cab","cba"]

思路：

老朋友回溯框架。

因为是排列，所以每次循环从0开始即可，不用从i(每个元素可重复选)或i+1(每个元素不可重复选)的情况开始。

因为不能有重复的排列，给的元素又可能是重复的，所以剪枝思路是先排序，限制每次填入的字符一定是这个字符所在重复字符集合中从左往右第一个未被填入的字符，比如aab，我们要先保证第一个a要先被使用，如果出现第一个a还没被使用，是不能把第二个a填进去的。

if(i>0&&chars[i]==chars[i-1]&&!flag[i-1]) continue;
1

代码：

class Solution {
    public String[] permutation(String s) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        boolean[] flag = new boolean[chars.length];
        StringBuilder sb = new StringBuilder();
        Set<String> res = new HashSet<>();
        backtrace(res,sb,chars,flag);
        return res.toArray(new String[0]);
    }

    public void backtrace(Set<String> res,StringBuilder sb,char[] chars,boolean[] flag){
        if(sb.length() == chars.length){
            res.add(sb.toString());
            return;
        }
        for(int i=0;i<chars.length;i++){
            //如果此时两个字符相等，但前一个还没被用，就不能用当前这一个
            if(i>0&&chars[i]==chars[i-1]&&!flag[i-1]){
                continue;
            }
            if(flag[i]){
                continue;
            }
            flag[i] = true;
            sb.append(chars[i]);
            backtrace(res,sb,chars,flag);
            flag[i] = false;
            sb.deleteCharAt(sb.length()-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

# 11.(medium)电话号码的字母组合

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

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

image-20220504212614039

思路：

和前面的组合问题一样，给定的字符串的长度，就是一种组合的长度，当path等于它的时候，加入到res即可；因为要保证不重复，所以每次递归从i+1开始，每次递归其实是选择的下一个字符串中的字符。比如2、3，第一次选了2中的a，进入递归其实是选择的3中的d

代码：

class Solution {
    List<String> res = new ArrayList<>();
    // 每个数字到字母的映射
    String[] mapping = new String[] {
         "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    };
    public List<String> letterCombinations(String digits) {
        if(digits.isEmpty()){
            return res;
        }
        backtrace(digits,new StringBuilder(),0);
        return res;
    }

    public void backtrace(String digits,StringBuilder path,int start){
        if(path.length() == digits.length()){
            res.add(path.toString());
            return;
        }
        for(int i=start;i<digits.length();i++){
            int digit = digits.charAt(i)-'2';
            for(int j=0;j<mapping[digit].length();j++){
                char ch = mapping[digit].charAt(j);
                path.append(ch);
                backtrace(digits,path,i+1);
                path.deleteCharAt(path.length() - 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

# 排列/组合/子集问题代码区别总结

由于子集问题和组合问题本质上是一样的，无非就是 base case 有一些区别，所以把这两个问题放在一起看。

# 形式一

元素无重不可复选，即 nums 中的元素都是唯一的，每个元素最多只能被使用一次，backtrace 核心代码如下：

/* 组合/子集问题回溯算法框架 */
void backtrace(int[] nums, int start) {
    // 回溯算法标准框架
    for (int i = start; i < nums.length; i++) {
        // 做选择
        track.addLast(nums[i]);
        // 注意参数
        backtrace(nums, i + 1);
        // 撤销选择
        track.removeLast();
    }
}

/* 排列问题回溯算法框架 */
void backtrace(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        // 剪枝逻辑
        if (used[i]) {
            continue;
        }
        // 做选择
        used[i] = true;
        track.addLast(nums[i]);
        backtrace(nums);
        // 取消选择
        track.removeLast();
        used[i] = false;
    }
}
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

# 形式二

元素可重不可复选，即 nums 中的元素可以存在重复，每个元素最多只能被使用一次，其关键在于排序和剪枝，backtrace 核心代码如下：

Arrays.sort(nums);
/* 组合/子集问题回溯算法框架 */
void backtrace(int[] nums, int start) {
    // 回溯算法标准框架
    for (int i = start; i < nums.length; i++) {
        // 剪枝逻辑，跳过值相同的相邻树枝
        if (i > start && nums[i] == nums[i - 1]) {
            continue;
        }
        // 做选择
        track.addLast(nums[i]);
        // 注意参数
        backtrace(nums, i + 1);
        // 撤销选择
        track.removeLast();
    }
}

Arrays.sort(nums);
/* 排列问题回溯算法框架 */
void backtrace(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        // 剪枝逻辑
        if (used[i]) {
            continue;
        }
        // 剪枝逻辑，固定相同的元素在排列中的相对位置
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
            continue;
        }
        // 做选择
        used[i] = true;
        track.addLast(nums[i]);
        backtrace(nums);
        // 取消选择
        track.removeLast();
        used[i] = false;
    }
}
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

# 形式三

元素无重可复选，即 nums 中的元素都是唯一的，每个元素可以被使用若干次，只要删掉去重逻辑即可，backtrace 核心代码如下：

/* 组合/子集问题回溯算法框架 */
void backtrace(int[] nums, int start) {
    // 回溯算法标准框架
    for (int i = start; i < nums.length; i++) {
        // 做选择
        track.addLast(nums[i]);
        // 注意参数
        backtrace(nums, i);
        // 撤销选择
        track.removeLast();
    }
}

/* 排列问题回溯算法框架 */
void backtrace(int[] nums) {
    for (int i = 0; i < nums.length; i++) {
        // 做选择
        track.addLast(nums[i]);
        backtrace(nums);
        // 取消选择
        track.removeLast();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 涉及二维数组

# 1.(medium)矩阵中的路径

image-20220402153657726

思路：

dfs回溯。

循环二维数组，从(0,0)开始查找。

边界条件：如果i，j越界，或者board[i] [j]不等于当前我们需要的word[index]，返回false。

如果index == word.length()-1，证明已经找到了，返回true。

查找时，先将当前位置标记为#表示已访问过，然后从上、下、左、右四个方位分别递归寻找，只要有一个返回true即可，找到后将当前的board[i] [j]还原为初始值，即word[index]

代码：

class Solution {
    String word;
    public boolean exist(char[][] board, String word) {
        this.word = word;
        for(int i=0;i<board.length;i++){
            for(int j=0;j<board[i].length;j++){
                if(backtarck(i,j,0,word.length(),board)){
                    return true;
                }
            }
        }
        return false;
    }

    public boolean backtarck(int i,int j,int index,int len,char[][] board){
        //如果越界或者当前字符与word[index]字符不等的时候 都false
        if(i<0||i>=board.length || j<0||j>=board[0].length ||board[i][j]!=word.charAt(index)){
            return false;
        }
        //找完了
        if(index == len-1){
            return true;
        }
        board[i][j] = '#';
        boolean res =  backtarck(i+1,j,index+1,len,board)||backtarck(i-1,j,index+1,len,board)
                        ||backtarck(i,j+1,index+1,len,board)||backtarck(i,j-1,index+1,len,board);
        board[i][j] = word.charAt(index);
        return res;
    } 
}
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

# 2.(medium)机器人的运动范围

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

示例 1：

输入：m = 2, n = 3, k = 1 输出：3 示例 2：

输入：m = 3, n = 1, k = 0 输出：1 提示：1 <= n,m <= 100,0 <= k <= 20

思路：dfs

首先是数位和的计算

public int sums(int x){
        int s = 0;
        while(x != 0) {
            s += x % 10;
            x = x / 10;
        }
        return s;
    }
1
2
3
4
5
6
7
8

定义dfs方法，返回void，从(0,0)开始搜索，如果i，j越界，或者flag[i] [j]为true((i,j)点已访问过)，或者i,j的数位和之和大于k，直接return，表示机器人不能走。

能走的时候，将当前flag[i] [j]=true，标记为已走过，然后将全局res++，从四个方向继续搜索即可

代码：

class Solution {
    int res = 0;
    public int movingCount(int m, int n, int k) {
        boolean[][] flag = new boolean[m][n];
        dfs(0,0,k,m,n,flag);
        return res;
    }

    public void dfs(int i,int j,int k,int m,int n,boolean[][] flag){
        //越界 或者已访问过 或者数位和大于k
        if(i<0||i>=m || j<0||j>=n || flag[i][j] || sums(i)+sums(j) > k){
            return;
        }
        flag[i][j] = true;
        res++;
        dfs(i+1,j,k,m,n,flag);
        dfs(i-1,j,k,m,n,flag);
        dfs(i,j-1,k,m,n,flag);
        dfs(i,j+1,k,m,n,flag);
    }

    public int sums(int x){
        int s = 0;
        while(x != 0) {
            s += x % 10;
            x = x / 10;
        }
        return 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

也可以改写为：

class Solution {
    public int movingCount(int m, int n, int k) {
        boolean[][] flag = new boolean[m][n];
        return dfs(0,0,k,m,n,flag);
    }

    public int dfs(int i,int j,int k,int m,int n,boolean[][] flag){
        //越界 或者已访问过 或者数位和大于k
        if(i<0||i>=m || j<0||j>=n || flag[i][j] || sums(i)+sums(j) > k){
            return 0;
        }
        flag[i][j] = true;
        return 1+dfs(i+1,j,k,m,n,flag)+
        dfs(i-1,j,k,m,n,flag)+
        dfs(i,j-1,k,m,n,flag)+
        dfs(i,j+1,k,m,n,flag);
    }

    public int sums(int x){
        int s = 0;
        while(x != 0) {
            s += x % 10;
            x = x / 10;
        }
        return 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

# 其他类型

# 1.(medium)求1+2+...+n(脑筋急转弯!)

求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

思路：

题目给了限制条件，那么循环那些肯定不能使用了，使用递归，但是递归需要base case，正常会想到用if，但if也禁止了，所以叫脑筋急转弯！

使用&&。因为 表达式a&&表达式b，如果表达式a的结果为false，那么表达式b并不会被执行，这样就可以用来结束递归了

代码：

class Solution {
    int res = 0;
    public int sumNums(int n) {
        //使用 && 当&&前为false，&&后的不会执行 即可将递归终止
        boolean b = n>1 && sumNums(n-1)>0;
        res+=n;
        return res;
    }
}
1
2
3
4
5
6
7
8
9

# 2(medium).单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。 注意，你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false

提示：

1 <= s.length <= 300 1 <= wordDict.length <= 1000 1 <= wordDict[i].length <= 20 s 和 wordDict[i] 仅有小写英文字母组成 wordDict 中的所有字符串 互不相同

思路：

一看想到了回溯，一开始的思路是，用对wordDict数组进行回溯，用它里面的单词进行组合，看能不能拼成字符串s，最后超时，如果数据量不大的话这种方式其实是可以暴力通过的。

下面说一下另一个方式，使用一个Set储存所有的单词，然后对目标字符串s进行遍历回溯，如果遍历到一个位置，从start到end这区间的能形成单词，即在Set中，那么这一段回溯返回true，这一段满足之后，就可以进入回溯下一段，最后直到遍历完目标字符串s，满足条件return true;

回溯树

可以很明显的看出需要剪枝的是在 wordDict 中找不到对应单词的分支

回溯三大步：

首先，「结束条件」是什么？显然是当把 s 全部遍历完之后就可以结束

其次，「选择列表」是什么？显然是 wordDict 中的单词集合

最后，「路径」是什么？显然是每一步从 wordDict 中选择的单词集合

代码：

class Solution {
    // 记录 [i...n-1] 是否可以拆分成单词
    // 0 : 表示还未处理该子问题；1 : 表示可以；-1 : 表示不可以
    int[] memo;
    Set<String> set = new HashSet<>();
    public boolean wordBreak(String s, List<String> wordDict) {
        for(String word : wordDict){
            set.add(word);
        }
        memo = new int[s.length()];
        Arrays.fill(memo, 0);
        return backtrace(s,0);
    }

    public boolean backtrace(String s, int index){
        if(index == s.length()){
            return true;
        }
        // 如果子问题已经处理过了，直接返回结果
        if(memo[index] != 0){
            return memo[index] == 1;
        }
        for(int i=index;i<s.length();i++){
            String temp = s.substring(index,i+1);
            if(!set.contains(temp)){
                continue;
            }
            //获取区间是否是一个单词的判断结果
            boolean pre = backtrace(s, i+1);
            if(pre){
                // 说明 [start...n-1] 是可以拆分成单词的
                memo[index] = 1;
                return true;
            }
        }
        // 已经完整遍历 [start...n-1] 都无法拆分
        memo[index] = -1;
        return false;
    }
}
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
在 GitHub 上编辑此页 (opens new window)
#回溯
最后更新: 2022/10/04, 16:10:00
动态规划
排序

← 排序→

Theme by Vdoing | Copyright © 2022-2024 zdk | notes
湘ICP备2022001117号-1
川公网安备 51142102511562号
提供加速服务