Post

回溯算法学习

Posted Updated
By Kurisu 27 min read

之前已经在二叉树的部分接触到了回溯算法，实际上回溯法解决的问题都可以抽象为树形结构，因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度，递归就要有终止条件，所以必然是一棵高度有限的树。

回溯三部曲：

  • 回溯函数模板返回值以及参数：回溯算法中函数返回值一般为void，但回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。
  • 回溯函数终止条件：什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。
  • 回溯搜索的遍历过程：回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。

总体框架为：

1
2
3
4
5
6
7
8
9
10
11
12

public void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择:本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径, 选择列表); // 递归
        回溯, 撤销处理结果
    }
}

组合问题

组合

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

  • 根据逻辑来决定参数：将问题抽象为树形结构，我们从左往右取数，取过的数不再取，发现n相当于树的宽度，k相当于树的深度，搜索到叶子节点便找到了一个结果，参数就可以是n、k、startIndex即从左往右取的第一个数。此外我们还定义全局变量res和path便于返回结果和回溯。
  • 终止条件：path如果大小为k，就说明到了叶子节点了，这是将path加入到res中就得到了结果之一。
  • 搜索过程：for循环进行横向遍历，递归进行纵向遍历，for循环每次从startIndex开始遍历，然后用path保存取到的节点i，递归往深处遍历，直到找到叶子节点。

本题还遇到了一个奇怪的问题，我直接result.add(path)是无法正常接收数据的，返回的结果数组全都没有元素，必须得new一个新对象才行。经查证仍然是引用传递的老问题，我们直接将path添加进去的话，path的修改会同时影响到result，之所以最后的结果全为空正是因为path回溯的最终状态就是空。

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

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

    public void backtracking(int n,int k,int startIndex){
        if (path.size() == k){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i =startIndex;i<=n;i++){
            path.add(i);
            backtracking(n,k,i+1);
            path.removeLast();
        }
    }
}

回溯离不开的就是剪枝操作，我们可以剪去可以百分百保证不会再有任何意义的树的遍历来改进性能。

可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。对于本题，如果for循环选择的起始位置之后的元素个数已经不足我们需要的元素个数了，那么就没有必要搜索了。

修改部分：

1
2
3
4

// 优化的地方
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) { 
    ......    
}

组合总和III

问题：找出所有相加之和为 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

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    List<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        backtracking(k, n, 1);
        return res;
    }
    public void backtracking(int k, int n, int startIndex) {
        if(n < 0) // 剪枝
            return ;
        if(path.size() == k && n == 0) { 
            res.add(new LinkedList(path)); 
            return ;
        }
        for(int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) { // 剪枝
            path.add(i);
            backtracking(k, n - i, i + 1);
            path.remove(path.size() - 1);
        }
    }
}

电话号码的字母组合

问题：给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

题意就是九键输入法中数字对应字母进行组合，做好数字和字母的映射，依然是回溯三部曲：

  • 确定回溯方法参数：本题以单个数字对应字符串作为宽度，数字个数作为深度，可看作树形结构，需要一个index标记深度即进行到哪个数字了
  • 确定终止条件：index等于数字字符串长度的时候就终止了。
  • 单层遍历逻辑：取index指向的数字，找到其对应的字符集，然后用for循环处理这个字符集。

代码示例：

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

class Solution {
    String[] numString = {
        "", // 0
        "", // 1
        "abc", // 2
        "def", // 3
        "ghi", // 4
        "jkl", // 5
        "mno", // 6
        "pqrs", // 7
        "tuv", // 8
        "wxyz", // 9
    };
    List <String> res= new LinkedList<>();
    StringBuilder temp = new StringBuilder();
    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 index) {
        //遍历全部一次记录一次得到的字符串
        if (index == digits.length()) {
            res.add(temp.toString());
            return;
        }
        //str 表示当前num对应的字符串
        String str = numString[digits.charAt(index) - '0'];
        for (int i = 0; i < str.length(); i++) {
            temp.append(str.charAt(i));
            //递归，处理下一层
            backTracking(digits, index + 1);
            //剔除末尾的继续尝试
            temp.deleteCharAt(temp.length() - 1);
        }
    }
}

组合总和II

问题：给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合，candidates 中的每个数字在每个组合中只能使用一次。所有数字（包括目标数）都是正整数，解集不能包含重复的组合。

这道题目特殊在不能包含重复的组合，需要我们进行去重处理。“使用过”在树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过，本题里，元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同，所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。
树层去重的话，需要对数组排序！还需要加一个bool型数组used，用来记录同一树枝上的元素是否使用过。如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，就说明：前一个树枝，使用了candidates[i - 1]，也就是说同一树层使用过candidates[i - 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

class Solution {
  LinkedList<Integer> path = new LinkedList<>();
  List<List<Integer>> ans = new ArrayList<>();
  boolean[] used;
  int sum = 0;

  public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    used = new boolean[candidates.length];
    // 加标志数组，用来辅助判断同层节点是否已经遍历
    Arrays.fill(used, false);
    // 为了将重复的数字都放到一起，所以先进行排序
    Arrays.sort(candidates);
    backTracking(candidates, target, 0);
    return ans;
  }

  private void backTracking(int[] candidates, int target, int startIndex) {
    if (sum == target) {
      ans.add(new ArrayList(path));
    }
    for (int i = startIndex; i < candidates.length; i++) {
      if (sum + candidates[i] > target) {
        break;
      }
      // 出现重复节点，同层的第一个节点已经被访问过，所以直接跳过
      if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {
        continue;
      }
      used[i] = true;
      sum += candidates[i];
      path.add(candidates[i]);
      // 每个节点仅能选择一次，所以从下一位开始
      backTracking(candidates, target, i + 1);
      used[i] = false;
      sum -= candidates[i];
      path.removeLast();
    }
  }
}

分割问题

分割回文串

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

切割问题类似组合问题。

  • 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个…..。
  • 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段…..。

所以切割问题也可以抽象为一棵树形结构。

回溯三部曲：

  • 递归函数参数：全局变量数组path存放切割后回文的子串，二维数组result存放结果集，本题递归函数参数还需要startIndex，因为切割过的地方，不能重复切割，和组合问题也是保持一致的。
  • 递归函数终止条件：切割线切到了字符串最后面，说明找到了一种切割方法，此时就是本层递归的终止条件。在处理组合问题的时候，递归参数需要传入startIndex，表示下一轮递归遍历的起始位置，这个startIndex就是切割线。
  • 单层搜索的逻辑：定义了起始位置startIndex，再通过i往树深处进行遍历，[startIndex, i] 就是要截取的子串首先判断这个子串是不是回文，如果是回文，就加入在vector path中，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
30
31
32
33
34
35
36
37
38

class Solution {
    List<List<String>> lists = new ArrayList<>();
    Deque<String> deque = new LinkedList<>();

    public List<List<String>> partition(String s) {
        backTracking(s, 0);
        return lists;
    }

    private void backTracking(String s, int startIndex) {
        //如果起始位置大于s的大小，说明找到了一组分割方案
        if (startIndex >= s.length()) {
            lists.add(new ArrayList(deque));
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            //如果是回文子串，则记录
            if (isPalindrome(s, startIndex, i)) {
                String str = s.substring(startIndex, i + 1);
                deque.addLast(str);
            } else {
                continue;
            }
            //起始位置后移，保证不重复
            backTracking(s, i + 1);
            deque.removeLast();
        }
    }
    //判断是否是回文串
    private boolean isPalindrome(String s, int startIndex, int end) {
        for (int i = startIndex, j = end; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }
}

复原IP地址

问题：给定一个只包含数字的字符串，复原它并返回所有可能的 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 地址。

同样也是切割问题，这道题难住我更多的是对于判断是否为有效IP该如何进行处理，以及如何妥善处理这个加进来的逗号，累积一下经验。

回溯三部曲：

  • 递归参数：startIndex一定是需要的，因为不能重复分割，记录下一层递归分割的起始位置。本题我们还需要一个变量pointNum，记录添加逗点的数量。
  • 递归终止条件：pointNum为3说明字符串分成了4段了，然后验证一下第四段是否合法，如果合法就加入到结果集里。
  • 单层搜索的逻辑：以startIndex做横向遍历，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
35
36
37
38
39
40
41

class Solution {
    List<String> result = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        StringBuilder sb = new StringBuilder(s);
        backTracking(sb, 0, 0);
        return result;
    }
    private void backTracking(StringBuilder s, int startIndex, int dotCount){
        if(dotCount == 3){
            if(isValid(s, startIndex, s.length() - 1)){
                result.add(s.toString());
            }
            return;
        }
        for(int i = startIndex; i < s.length(); i++){
            if(isValid(s, startIndex, i)){
                s.insert(i + 1, '.');
                backTracking(s, i + 2, dotCount + 1);
                s.deleteCharAt(i + 1);
            }else{
                break;
            }
        }
    }
    //[start, end]
    private boolean isValid(StringBuilder s, int start, int end){
        if(start > end)
            return false;
        if(s.charAt(start) == '0' && start != end)
            return false;
        int num = 0;
        for(int i = start; i <= end; i++){
            int digit = s.charAt(i) - '0';
            num = num * 10 + digit;
            if(num > 255)
                return false;
        }
        return true;
    }
}

子集问题

子集

问题：给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。

和组合问题类似，区别在于不只是对叶子节点进行处理，而是遍历整棵树，对每一个节点都要加入返回结果。问题在于什么时候加入返回结果呢，若是在循环里或者终止条件之后加，会出现漏掉最后一个元素本身的情况，所以要加在最前面。

代码示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
    LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
    public List<List<Integer>> subsets(int[] nums) {
        subsetsHelper(nums, 0);
        return result;
    }

    private void subsetsHelper(int[] nums, int startIndex){
        result.add(new ArrayList<>(path));//「遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合」。
        if (startIndex >= nums.length){ //终止条件可不加
            return;
        }
        for (int i = startIndex; i < nums.length; i++){
            path.add(nums[i]);
            subsetsHelper(nums, i + 1);
            path.removeLast();
        }
    }
}

子集II

问题：给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。

和组合II类似，我们要去考虑去重的问题。去重首先要对数组进行排序，引入used数组标记元素是否被使用过了，对于树层去重，满足nums[i] == nums[i-1] && used[i-1] == 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
30
31
32

class Solution {
   List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
   LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
   boolean[] used;
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        if (nums.length == 0){
            result.add(path);
            return result;
        }
        Arrays.sort(nums);
        used = new boolean[nums.length];
        subsetsWithDupHelper(nums, 0);
        return result;
    }
    
    private void subsetsWithDupHelper(int[] nums, int startIndex){
        result.add(new ArrayList<>(path));
        if (startIndex >= nums.length){
            return;
        }
        for (int i = startIndex; i < nums.length; i++){
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            subsetsWithDupHelper(nums, i + 1);
            path.removeLast();
            used[i] = false;
        }
    }
}

排列问题

全排列

问题：给定一个 没有重复 数字的序列，返回其所有可能的全排列。

全排列和组合问题不同的是，其序列是有顺序的，[1, 2] [2, 1]是不同两个排列，所以for循环里不用startIndex了，而是用一个used数组记录此时path里都有哪些元素使用了。

  • 递归函数参数：需要一个used数组。
  • 递归终止条件：当收集元素的数组path的大小达到和nums数组一样大的时候，说明找到了一个全排列，也表示到达了叶子节点。
  • 单层搜索的逻辑：使用used数组进行判断是否加入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
30
31

class Solution {

    List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
    LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
    boolean[] used;
    public List<List<Integer>> permute(int[] nums) {
        if (nums.length == 0){
            return result;
        }
        used = new boolean[nums.length];
        permuteHelper(nums);
        return result;
    }

    private void permuteHelper(int[] nums){
        if (path.size() == nums.length){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++){
            if (used[i]){
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            permuteHelper(nums);
            path.removeLast();
            used[i] = false;
        }
    }
}

全排列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>> result = new ArrayList<>();
    //暂存结果
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] used = new boolean[nums.length];
        Arrays.fill(used, false);
        Arrays.sort(nums);
        backTrack(nums, used);
        return result;
    }

    private void backTrack(int[] nums, boolean[] used) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            // used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过
            // used[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过
            // 如果同⼀树层nums[i - 1]使⽤过则直接跳过
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            //如果同⼀树⽀nums[i]没使⽤过开始处理
            if (used[i] == false) {
                used[i] = true;//标记同⼀树⽀nums[i]使⽤过，防止同一树枝重复使用
                path.add(nums[i]);
                backTrack(nums, used);
                path.remove(path.size() - 1);//回溯，说明同⼀树层nums[i]使⽤过，防止下一树层重复
                used[i] = false;//回溯
            }
        }
    }
}

其他问题

递增子序列

问题：给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。

和子集问题去重不同，这道题目不可以对原数组进行排序，因为是要求原数组里的递增子序列，这里考虑使用HashSet记录元素进行去重，同时题目给元素限定了-100~100的范围，也可以考虑使用数组做哈希。其他和前面的题目没什么太大差别。

代码示例：

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>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        backTracking(nums, 0);
        return result;
    }
    private void backTracking(int[] nums, int startIndex){
        if(path.size() >= 2)
                result.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.remove(path.size() - 1);
        }
    }
}
学习, 算法
算法
This post is licensed under CC BY 4.0 by the author.

Trending Tags

算法 ACG 技术 生活 小记