回溯算法问题汇总

深碍√TFBOYSˉ_ 2024-03-27 16:38 73阅读 0赞

#### 文章目录 ####

*  模版
 *  一. 组合问题
 *   *  77. 组合
     *  216.组合总和III
     *  17.电话号码的字母组合
     *  39. 组合总和
     *  40.组合总和II
     *  131.分割回文串
     *  93.复原IP地址
     *  78.子集
     *  90.子集II
     *  491.递增子序列
     *  46.全排列
     *  47.全排列 II
     *  332.重新安排行程
     *  51. N皇后
     *  37. 解数独

## 模版 ##

void backtracking(参数) {
        
        if (终止条件) {
        
            存放结果;
            return;
        }
    
        for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        
            处理节点;
            backtracking(路径，选择列表); // 递归
            回溯，撤销处理结果
        }
    }

![在这里插入图片描述][6e35cde35ed546d988b1d72ae7f00c2b.png]

## 一. 组合问题 ##

回溯法，一般可以解决如下几种问题：

> 组合问题：N个数里面按一定规则找出k个数的集合  
> 切割问题：一个字符串按一定规则有几种切割方式  
> 子集问题：一个N个数的集合里有多少符合条件的子集  
> 排列问题：N个数按一定规则全排列，有几种排列方式  
> 棋盘问题：N皇后，解数独等等

**组合是不强调元素顺序的，排列是强调元素顺序。**

例如：\{1, 2\} 和 \{2, 1\} 在组合上，就是一个集合，因为不强调顺序，而要是排列的话，\{1, 2\} 和 \{2, 1\} 就是两个集合了。

记住组合无序，排列有序，就可以了

### 77. 组合 ###

![在这里插入图片描述][44a3867dbfaa44f8b903d99d1d1636c6.png]

class Solution {
        
        public List<List<Integer>> combine(int n, int k) {
        
            if(n<k){
        
                return lists;
            }
    
            find(n,1,k);
            return lists;
        }
    
        private void find(int n, int begin,int k){
        
            if(k == 0){
        
                lists.add(new ArrayList<>(list));
                return;
            }
            if(begin > n){
        
                return;
            }
            for(int i=begin;i<=n;i++){
        
                //如果后面的数不够了，就不用考虑了
                if(n-i+1 < k){
        
                    return;
                }
    
                // 将当前数放入list
                list.add(i);
                k--;
                find(n,i+1,k);
                k++;
                list.remove(list.size()-1);
            }
        }
    
    
        private List<List<Integer>> lists = new ArrayList<List<Integer>>();
        private List<Integer> list = new ArrayList<>();
    }

做了简单的剪枝，如果剩余的元素加上已选中的元素，不够凑成k个，那就直接返回。

### 216.组合总和III ###

![在这里插入图片描述][fb1a0696c65246b887a3ee4058d559fa.png]

class Solution {
        
        public List<List<Integer>> combinationSum3(int k, int n) {
        
            find(1,k,n);
            return list;
        }
    
        private void find(int begin,int k, int sub){
        
            //如果减成了负数，直接返回
            if(sub<0){
        
                return;
            }
            if(sub==0 && path.size() == k){
        
                list.add(new ArrayList<>(path));
                return;
            }
    
            for(int i=begin;i<10;i++){
        
                // 直接减
                path.add(i);
                sub -= i;
                find(i+1,k,sub);
                sub += i;
                path.remove(path.size()-1);
            }
        }
    
        private List<List<Integer>> list = new ArrayList<List<Integer>>();
        private List<Integer> path = new ArrayList<Integer>();
    }

### 17.电话号码的字母组合 ###

![在这里插入图片描述][5a3aff51053048d78215fcacab88dd78.png]

class Solution {
        
        public List<String> letterCombinations(String digits) {
        
            if(digits == "" || digits == null || digits.length() == 0){
        
                return new ArrayList<String>();
            }
            
            find(0,digits);
            return list;
    
        }
    
        private void find(int index,String digits ){
        
            if(index == digits.length()){
        
                list.add(path.toString());
                return;
            }
    
            String str = map[Integer.parseInt(String.valueOf(digits.charAt(index)))];
    
            for(int i=0;i<str.length();i++){
        
                path.append(str.charAt(i));
                find(index+1,digits);
                path.deleteCharAt(path.length()-1);
            }
        }
    
        // 预先放入数组中，然后根据字符串数字-数组序列号取出
        private String[] map =  new String[]{
        
        "", // 0
        "", // 1
        "abc", // 2
        "def", // 3
        "ghi", // 4
        "jkl", // 5
        "mno", // 6
        "pqrs", // 7
        "tuv", // 8
        "wxyz", // 9
        };
    
        private List<String> list = new ArrayList<>();
        private StringBuilder path = new StringBuilder();
    }

### 39. 组合总和 ###

![在这里插入图片描述][4206ca3d935345ac9e0583f9ec453924.png]

class Solution {
        
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
        
            Arrays.sort(candidates);
            find(0,candidates,target);
            return lists;
        }
    
        private void find(int begin,int[] candidates,int target){
        
            if(target == 0){
        
                lists.add(new ArrayList<>(path));
                return; 
            }
            if(target<0 || begin >= candidates.length){
        
                return;
            }
    
            for(int i=begin;i<candidates.length;i++){
        
                // 剪枝，如果我已经比它小了，后面更大的数你就不用考虑了
                if(candidates[i] > target){
        
                    return;
                }
                target -= candidates[i];
                path.add(candidates[i]);
                // 由于可以重复取数，所以没有i+1
                find(i,candidates,target);
                path.remove(path.size()-1);
                target += candidates[i];
            }
        }
    
        private List<List<Integer>> lists = new ArrayList<List<Integer>>();
        private List<Integer> path = new ArrayList<Integer>();
    }

### 40.组合总和II ###

![在这里插入图片描述][39d5f6e7aae64bfe8be102d70e730204.png]

class Solution {
        
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        
            Arrays.sort(candidates);
            used = new int[candidates.length];
            find(0,candidates,target);
            return lists;
        }
    
        private void find(int begin, int[] candidates,int target){
        
            // 如果减完了，结束
            if(target == 0){
        
                lists.add(new ArrayList(path));
                return;
            }
    
             // 如果搜完了或者已经成了负数，结束
            if(target<0 || begin >= candidates.length){
        
                return;
            }
    
    
            for(int i=begin;i<candidates.length;i++){
        
                // 如果是重复的数字，同一层的搜过了就别搜我了，谢谢
                // 比如 2 2 ，如果是同一层的搜过了那它就used=0,但如果是递归下来的，就是used=1
                // 注意continue和return 这个for循环相同于横向的一个遍历，如果到这一步横向的后面节点不用了就return，如果只是跳过这个节点继续去执行横向的下个节点，则用continue
                if(i>0 && candidates[i] == candidates[i-1] && used[i-1]==0){
        
                    continue;
                }
    
                // 如果我已经比target大了，那就别考虑我了，我后面更大的也别考虑（已排序）
                if(candidates[i] > target){
        
                    return;
                }
                // 如果我被用过了，千万别用我
                if(used[i] == 1){
        
                    continue;
                }
    
                target-=candidates[i];
                used[i]=1;
                path.add(candidates[i]);
                find(i+1,candidates,target);
                used[i]=0;
                target+=candidates[i];
                path.remove(path.size()-1);
            }
        }
    
        private List<List<Integer>> lists = new ArrayList<List<Integer>>();
        private List<Integer> path = new ArrayList<Integer>();
        private int[] used;
    }

![在这里插入图片描述][37de482542ac4e1eac6d563295989044.png]

### 131.分割回文串 ###

![在这里插入图片描述][a113e4d5e98e40038e40998c2ec95a6b.png]

class Solution {
        
        public List<List<String>> partition(String s) {
        
            if(s == null || s.length() == 0){
        
                return lists;
            }
            find(0,s);
            return lists;
        }
    
        private void find(int begin, String s){
        
    
            // 如果切割到底了，且都是回文，则成功
            if(begin == s.length()){
        
                lists.add(new ArrayList<>(path));
                return;
            }
    
            for(int i=begin;i<s.length();i++){
        
                // 切割i下标
                // 如果非回文，直接跳过，去截取后面的吧
                if(!isReverse(s,begin,i)){
        
                    continue;
                }
                path.add(s.substring(begin,i+1));
                find(i+1,s);
                path.remove(path.size()-1);
            }
        }
    
        // 判断是否是回文
        private boolean isReverse(String s,int begin, int end) {
        
            for (int i = begin, j = end; i < j; i++, j--) {
        
                if (s.charAt(i) != s.charAt(j)) {
        
                    return false;
                }
            }
            return true;
        }
    
    
        private List<List<String>> lists = new ArrayList<List<String>>();
        private List<String> path = new ArrayList<String>();
        
    }

![在这里插入图片描述][8894ba5092394c28a33fcabc4b5c159c.png]

### 93.复原IP地址 ###

![在这里插入图片描述][ad96df4276dc4bf481a6d2f01fa18e05.png]

class Solution {
        
          public List<String> restoreIpAddresses(String s) {
        
            //如果字符串长度小于4或大于12，则不符合
            if(s == null || s.length() < 4 || s.length() > 12){
        
                return list;
            }
            find(0,s);
            return list;
    
        }
    
        private void find(int begin,String s){
        
            // 如果剩余的字符串长度不能满足剩下的ip分配，或者太多了,则结束
            if((s.length()-begin) < (4-path.size()) || (s.length()-begin) > (4-path.size()) * 3){
        
                return;
            }
    
    
    
            // 如果list长度为3，说明是最后一个了，可以加进去了
            if(path.size()==3){
        
                String str = s.substring(begin);
                if(!isVaild(str)){
        
                    return;
                }
               
                path.add(str);
                list.add(pathToList(path));
                path.remove(path.size()-1);
                return;
            }
    
            // 循环切割
            for(int i=begin;i<s.length() && i<=begin+2;i++){
        
    
                String str = s.substring(begin,i+1);
                // 如果不满足大小，结束
                if(!isVaild(str)){
        
                    continue;
                }
    
                path.add(str);
                find(i+1,s);
                path.remove(path.size()-1);
            }
    
        }
    
        // 判断切割的字符串是否合法
        private boolean isVaild(String str){
        
            // 不可用是以0开头的多位数
            if(str.charAt(0) == '0' && str.length() > 1){
        
                    return false;
            }
            // 判断该数字是否不大于255
            return Integer.parseInt(str) <= 255;
        }
        
    
        // 将path转化为地址ip字符串
        private String pathToList(List<String> path){
        
            StringBuilder str = new StringBuilder();
            path.forEach(p -> {
        
                str.append(p).append(".");
            });
            str.deleteCharAt(str.length()-1);
            return str.toString();
        }
    
        private List<String> list = new ArrayList<String>();
        private List<String> path = new ArrayList<String>();
        private StringBuilder str = new StringBuilder();
    
    }

### 78.子集 ###

![在这里插入图片描述][aacc0002c5364c0a95b6477d06bb88e1.png]

class Solution {
        
        public List<List<Integer>> subsets(int[] nums) {
        
           find(0,nums);
           return list;
        }
    
        public void find(int begin, int[] nums){
        
        // 一进来就直接加入，这个的区别就是所有的树节点全部算上
            list.add(new ArrayList<>(path));
    
           for(int i=begin;i<nums.length;i++){
        
               path.add(nums[i]);
               find(i+1,nums);
               path.remove(path.size()-1);
           }
        }
    
        private List<List<Integer>> list = new ArrayList<List<Integer>>();
        private List<Integer> path = new ArrayList<Integer>(); 
    }

![在这里插入图片描述][e0635e3f683945f587e608e1458c1ef2.png]  
**之前的题目都是最后的叶子结点就是答案，子集问题是把所有的结点全部算上才行。**

### 90.子集II ###

![在这里插入图片描述][a8b88b9e20444678bdfa631d50d2b36b.png]

class Solution {
        
        public List<List<Integer>> subsetsWithDup(int[] nums) {
        
            Arrays.sort(nums);
            used = new int[nums.length];
            find(0,nums);
            return list;
        }
    
    
        // 递归枚举nums[0]、nums[1]、、、nums[n-1]这n个数选或不选
        public void find(int begin, int[] nums){
        
            list.add(new ArrayList<>(path));
            
            for(int i=begin;i<nums.length;i++){
        
                if(i>0&&nums[i]==nums[i-1]&&used[i-1]==0){
        
                    continue;
                }
                path.add(nums[i]);
                used[i]=1;
                find(i+1, nums);
                used[i]=0;
                path.remove(path.size() - 1);
            }
        }
        private List<List<Integer>> list = new ArrayList<List<Integer>>();
        private List<Integer> path = new ArrayList<Integer>(); 
        int[] used;
    }

### 491.递增子序列 ###

![在这里插入图片描述][1b6513c3dbf2433eb34644d5d1b81f05.png]

class Solution {
        
        public List<List<Integer>> findSubsequences(int[] nums) {
        
            find(0,nums);
            return list;
        }
    
        private void find(int begin, int[] nums){
        
    
            // 如果当前数大于上一个数，则直接加入path，取的树上所有节点
            if(path.size() >= 2){
        
                list.add(new ArrayList<>(path));
            }
            // 局部变量，只用于该层的遍历
            int[] used = new int[201];
            for(int i=begin;i<nums.length;i++){
        
                //在该层的遍历中，相同元素不需要重复再执行
                if(i>0 && used[nums[i]+100]==1){
        
                    continue;
                }
                if(path.size()>0 && nums[i] < path.get(path.size()-1)){
        
                    continue;
                }
                used[nums[i]+100]=1;
                path.add(nums[i]);
                find(i+1,nums);
                path.remove(path.size()-1);
            }
        }
    
        private List<List<Integer>> list = new ArrayList<List<Integer>>();
        private List<Integer> path = new ArrayList<Integer>(); 
        
    }

本题的used是局部变量，每层迭代的时候会重新定义，用于每一层的遍历。  
同时，答案是收集到所有的树节点。  
不理解的画个树图。

### 46.全排列 ###

![在这里插入图片描述][203cc3c6f0f74f0e957ff7e7a8ae4d49.png]

class Solution {
        
        public List<List<Integer>> permute(int[] nums) {
        
            used = new int[nums.length];
            find(0,nums);
            return list;
        }
    
    // 每次从没选中的里面选一个，index无限递增，知道list的size为n
        private void find(int index, int[] nums){
        
            if(index == nums.length){
        
                list.add(new ArrayList<>(path));
                return;
            }
            for(int i=0;i<nums.length;i++){
        
                // 如果未选过，则选
                if(used[i] == 1){
        
                    continue;
                 }
                path.add(nums[i]);
                used[i] = 1;
                find(index+1, nums);
                path.remove(path.size()-1);
                used[i] = 0;
            } 
        }
    
    
    
        private List<List<Integer>> list = new ArrayList<List<Integer>>();
        private List<Integer> path = new ArrayList<Integer>(); 
        private int[] used;
    
    }

### 47.全排列 II ###

![在这里插入图片描述][f6e52553c64542ef91790826286a24be.png]

class Solution {
        
        public List<List<Integer>> permuteUnique(int[] nums) {
        
            used = new int[nums.length];
            Arrays.sort(nums);
            find(0,nums);
            return list;
        }
    
        private void find(int index, int[] nums){
        
            if(path.size() == nums.length){
        
                list.add(new ArrayList<Integer>(path));
                return;
            }
    
            for(int i=0;i<nums.length;i++){
        
                // 如果未使用，赶紧用
                if(used[i] == 1){
        
                    continue;
                }
                if(i>0 && nums[i]==nums[i-1]&&used[i-1]==0){
        
                    continue;
                }
                used[i]=1;
                path.add(nums[i]);
                find(index+1,nums);
                path.remove(path.size()-1);
                used[i]=0;
            }
        }
        private List<List<Integer>> list = new ArrayList<List<Integer>>();
        private List<Integer> path = new ArrayList<Integer>(); 
        private int[] used;
    }

### 332.重新安排行程 ###

![在这里插入图片描述][5495c8c2ab1d46c8ae58641547b72e5c.png]  
缺乏之前知识，后续再做

### 51. N皇后 ###

![在这里插入图片描述][0c16f8d2f4cf40edb4e9318f5d323223.png]

class Solution {
        
       public List<List<String>> solveNQueens(int n) {
        
            // 横向的已占的皇后节点
            used = new int[n];
            String[][] nums = new String[n][n];
            init(nums);
            find(nums,0);
            return list;
        }
    
        private void find(String[][] nums,int index){
        
            // 迭代结束
            if(index == nums.length){
        
                list.add(numToList(nums));
                return;
            }
    
            // 如果这个点不符合皇后范围，则舍弃
            for(int i=0;i<nums.length;i++){
        
                if(isValid(nums,index,i)){
        
                    used[i]=1;
                    nums[index][i] = "Q";
                    // 最重要的地方，这里是index+1！！！！
                    find(nums,index+1);
                    used[i]=0;
                    nums[index][i] = ".";
                }
    
            }
    
    
        }
        private boolean isValid(String[][] chessboard, int row, int col){
        
            // 单独检查列
            if(used[col]==1){
        
                return false;
            }
    
            // 检查45度对角线
            for (int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) {
        
                if (chessboard[i][j] == "Q") {
        
                    return false;
                }
            }
    
            // 检查135度对角线
            for (int i=row-1, j=col+1; i>=0 && j<=chessboard.length-1; i--, j++) {
        
                if (chessboard[i][j] == "Q") {
        
                    return false;
                }
            }
            return true;
        }
    
        // 初始化二维数组为全部"."
        private void init(String[][] str){
        
            for (int i = 0; i < str.length; i++) {
        
                for (int j = 0; j < str.length; j++) {
        
                    str[i][j] = ".";
                }
            }
        }
        // 将数组转变成返回值要求的String
        private List<String> numToList(String[][] str){
        
            List<String> list = new ArrayList<>();
            for (int i = 0; i < str.length; i++) {
        
                StringBuilder s = new StringBuilder();
                for (int j = 0; j < str.length; j++) {
        
                    s.append(str[i][j]);
                }
                list.add(s.toString());
            }
            return list;
        }
        private List<List<String>> list = new ArrayList<List<String>>();
        int[] used;  
    }

不难，但是复杂。  
每次迭代是index+1,而不是之前的i+1，切记！

### 37. 解数独 ###

![在这里插入图片描述][3a185e0e5f044251aa7989409beffff2.png]  
缺乏前面知识，后续再做

[6e35cde35ed546d988b1d72ae7f00c2b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/c1a1510b945042639aa98f9df1761736.png
[44a3867dbfaa44f8b903d99d1d1636c6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/437ce1bfd5894e03b14d3ec5c88f9e34.png
[fb1a0696c65246b887a3ee4058d559fa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/c33def7a46ab4e6885269522596bd0e4.png
[5a3aff51053048d78215fcacab88dd78.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/4052b47d6a3d46d0bdd0cece2153aa0b.png
[4206ca3d935345ac9e0583f9ec453924.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/b912424ca938492db303d71be7d910a7.png
[39d5f6e7aae64bfe8be102d70e730204.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/802741938d8543f884c37fbe22c484aa.png
[37de482542ac4e1eac6d563295989044.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/c138c130b5904676a13c834e12581535.png
[a113e4d5e98e40038e40998c2ec95a6b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/174bf5aff7d241339019035132482d6d.png
[8894ba5092394c28a33fcabc4b5c159c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/432b1db4ec0d446296a30cf4dc6a9790.png
[ad96df4276dc4bf481a6d2f01fa18e05.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/0d9485a3ffe341dbb9ea2c7dc41b6ba2.png
[aacc0002c5364c0a95b6477d06bb88e1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/0d34bc81b06f467296901061f9479a5a.png
[e0635e3f683945f587e608e1458c1ef2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/1b1f64f8ea304106bc45bbb65056bee5.png
[a8b88b9e20444678bdfa631d50d2b36b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/9fdfbf2aab344aaca1305a223f03fde3.png
[1b6513c3dbf2433eb34644d5d1b81f05.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/ecc2ffdd51e04c4cb30e0a22b3ab0294.png
[203cc3c6f0f74f0e957ff7e7a8ae4d49.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/e9c40aa01e9e497e83c1d964c5eeee9c.png
[f6e52553c64542ef91790826286a24be.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/ea5736ae495e4a29a60edb8514b4853f.png
[5495c8c2ab1d46c8ae58641547b72e5c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/5e2fd54d6f3648c3b9337604b876d31a.png
[0c16f8d2f4cf40edb4e9318f5d323223.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/e8e7810d706e43a5bb1e5ee505c36ff3.png
[3a185e0e5f044251aa7989409beffff2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/ac657829e29b4eb8b44929fe4bb3d325.png