回溯剪枝 | tsuki's CodeLife

刚开始刷题大部分都不会，有的题有思路但是代码写不明白，参考了很多官方和评论区大佬的答案，学到了很多。解答用的语言是c++，在边学边用，官方的STL库还不熟悉，菜鸟如我经常搞错vector的用法。

本来打算九月底发的博客拖到了现在(十一月初），十月也没有继续刷题。开始准备做项目不由感叹门外汉入门真是不容易，什么都不会，扶额。

这一个月做过的题类型有，回溯算法加剪枝，二叉树的遍历和递归，并查集等等。

2022 用Java重刷一遍，修改了内容。

回溯算法加剪枝

一直碰到用回溯算法就歇菜。现在还没有完全掌握。

回溯算符与递归的区别在于，回溯过程中达到结束条件要恢复状态回溯到上一层，再次搜索，而递归是一个劲往某个方向。回溯与DFS的区别就是有无状态的重置。

在题解区看到答主的回答颇有所获，非常感谢。但是实际应用中画出递归树不好理解。

1.DFS 和回溯算法区别
DFS 是一个劲的往某一个方向搜索，而回溯算法建立在 DFS 基础之上的，但不同的是在搜索过程中，达到结束条件后，恢复状态，回溯上一层，再次搜索。因此回溯算法与 DFS 的区别就是有无状态重置

2.何时使用回溯算法
当问题需要 “回头”，以此来查找出所有的解的时候，使用回溯算法。即满足结束条件或者发现不是正确路径的时候(走不通)，要撤销选择，回退到上一个状态，继续尝试，直到找出所有解为止

子集和组合

对于这类寻找所有可行解的题都可以用回溯来解决。

78. 子集补充一点Java的解决方案，思路是一样的。

public void dfs(int curr, int[] nums){
    if(curr == nums.length){
        ret.add(new ArrayList<Integer>(path));
        return;
    }
    path.add(nums[curr]);
    dfs(curr+1, nums);//选择
    path.remove(path.size() - 1);
    dfs(curr+1, nums);//不选择
}

90. 子集 II使用了剪枝。使用了start变量。

参考了官方的答案，递归枚举类题的包括以下几个步骤：

画出递归树（关键
递归边界，记录的条件
设置了vector: temp当前的记录，vector<vector<>>: ret返回所有的记录

判断是否需要剪枝处理

sort(nums.begin(), nums.end());
if(i > start && nums[i] == nums[i - 1]){
    continue;
}

组合中可以选择或者不选择当前位置，之后递归考虑下一个位置。
1
2
3
4
temp.push_back(cur);
dfs(cur + 1);
temp.pop();
dfs(cur + 1);

（事实告诉我们不要写一半跑路，时隔一个月我已经看不懂之前写的了，趁着快要考试继续做算法总结

递归的解法中，关键在于这句话*，对于当前选择的数curr，若前面有与其相同的数pre，且没有选择pre，此时包含curr的子集，必然会出现在包含pre的所有子集中。

所以设置了一个boolean位判断是否选择了之前同值的数。官解有点费解，本题解借鉴了更易懂的写法。

public void dfs(int start, int[] nums){       
    if(start == nums.length){
        ret.add(new ArrayList<Integer>(path));
        return;
    }
    path.add(nums[start]);//选择
    dfs(start + 1, nums);

    path.remove(path.size() - 1);//回溯，不选择
    //跳过重复值      
    while(start < (nums.length - 1) && nums[start] == nums[start + 1]){
        start++;
    }
    dfs(start + 1, nums);     
}

组合中配合使用了剪枝来减少时间。

39. 组合总和中传入了target变量。

补充递归解法，选择和不选择，ret和path作为全局变量定义在方法外。

public void dfs(int[] candidates, int target, int index){
    if(index == candidates.length) return;
    if(target == 0){
        ret.add(new ArrayList<Integer>(path));
        return;
    }
    //不选择
    dfs(candidates, target, index + 1);
    //选择,包含=，因为路径还没加入ret
    if(target - candidates[index] >= 0 ){
        path.add(candidates[index]);
        dfs(candidates, target-candidates[index], index);
        path.remove(path.size() - 1);
    }        
}

组合总和2使用了剪枝。

全排列

46. 全排列 Java版本也是一样的思路，设置used数组。这一题是不需要剪枝的，思路比较简单。

47. 全排列 II设置了visited数组。

核心代码如下：

for(int i = 0; i < nums.size(); i++){
    if(visited[i] == true) continue;
    visited[i] = true;
    temp.push_back();
    dfs();
    visited[i] = false;//回退
    temp.pop_back();
}

考虑剪枝处理

sort(nums.begin(), nums.end());
// i > 0 是为了i - 1 有效
if(i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]){
    continue;
}

Java版本

public void backtrace(int[] nums, boolean[] used){
    if(path.size() == nums.length){
        ret.add(new ArrayList<Integer>(path));
        return;
    }
    for(int i = 0; i < nums.length; i++){
        if(!used[i]){
            if(i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            backtrace(nums, used);
            used[i] = false;
            path.remove(path.size() - 1);
        }
    }
}

剑指 Offer 38. 字符串的排列和全排列的思路几乎一样。在于字符串api的熟练使用。字符串问题一般是转为字符数组来解决。StringBuffer用法

   StringBuffer path = new StringBuffer();
   char[] chars = s.toCharArray();
   //List<String>转为String[]
   String[] ans = new String[ret.size()];
   for(int i = 0; i < ret.size(); i++){
       ans[i] = ret.get(i);
   }

path.append(chars[i]);
path.deleteCharAt(path.length() - 1);

搜索

参考博文

37. 解数独这是道困难，一整个震惊之前居然做过，毫无印象。回溯，标记状态位，不过是比较复杂的情况。行标记，列标记，以及块标记，将空白待添块添加到队列，逐个筛查。

79. 单词搜索有点类似数独，小tip，可以用 int[][] directions = {/{0, 1}, {0, -1}, {1, 0}, {-1,0}/}; 表示网格的上下左右四个方向，还有一些小细节，越界判断，if(newi >= 0 && newi < board.length && newj >=0 && newj < board[0].length)和check结果的if判断，直接return会丢失一些结果。

51. N 皇后

法一，基于集合的回溯剪枝。变量很多，但是思路不变，行优先，逐行填入。有一个难点是怎么确定对角线是否已经被占用，左上到右下的对角线，行坐标-纵坐标的差相等，左下到右上对角线，行坐标+纵坐标的和相等。基于集合用到了HashSet。难点二生成返回的board结合。

        Set<Integer> columns = new HashSet<>();
        Set<Integer> diagonals1 = new HashSet<>();
        Set<Integer> diagonals2 = new HashSet<>();
        int[] queens = new int[n];
        Arrays.fill(queens, -1);
		backtrack(ret, queens, 0, n, columns, diagonals1, diagonals2);

//生成board
    public List<String> generateBoard(int[] queens, int n){
        List<String> board = new ArrayList<>();
        for(int i = 0; i < n; ++i){
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[queens[i]] = 'Q';
            board.add(new String(row));
        }
        return board;
    }

法二基于位运算的回溯。（待完成

面试题 08.12. 八皇后就是上一道N皇后本尊。

131. 分割回文串官解给的是回溯加动态规划预处理，但是本菜鸡还是先用回溯直接做了。重点在于子串。

public void backtrack(String s, int start){
    if(start == s.length()){
        ret.add(new ArrayList<String>(segments));
        return;
    }
    
    for( int end = start; end < s.length(); ++end){
        String sub = s.substring(start, end + 1);//子串
        //剪枝判断
        if(!isPalindrome(sub)){
            continue;
        }
        segments.add(sub);
        backtrack(s, end + 1);
        segments.remove(segments.size() - 1);
    }

}

93. 复原 IP 地址和分割回文串应该是一类题。return的情况要考虑全。

401. 二进制手表

递归

层次遍历

二叉树层次遍历和层次相关时，可以用queue.size()获取一层的个数，一层一层的处理。如leetcode 637，二叉树层平均值，leetcode 117，层链接

相关于二叉树的题十有八九是递归算法，属于有思路但是写出来的代码总有逻辑错误的题，栈溢出，多半是递归边界问题，还有递归的参数没弄对。

回溯算法加剪枝

子集和组合

全排列

搜索

递归

分治