day35——回溯专题

水深无声 2024-03-31 10:08 71阅读 0赞

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

*   *  分割问题
     *   *  7. 分割回文串
         *  8. 复原IP地址
     *  子集问题
     *   *   *  9. 子集I
             *  10.子集II

--------------------

### 分割问题 ###

#### 7. 分割回文串 ####

题目链接：[131. 分割回文串 - 力扣（LeetCode）][131. _ - _LeetCode]

枚举方案类的题目都可以用回溯法来实现，枚举该串的所有子串，判断子串是否是回文串即可！

**回溯三部曲**

*  递归函数参数

public void dfs(String s, int startIndex){
        
     }

*  递归函数终止条件

![image-20221122092926063][]

if(startIndex==n){
        
                res.add(new ArrayList(path));
                return ;
            }

*  单层搜索的逻辑

for(int i = startIndex; i<n; i++){
        
                if(is_huiwen(s.substring(startIndex,i+1))){
        
                    path.add(s.substring(startIndex,i+1));
                    dfs(s,i+1);
                    path.remove(path.size()-1);

**Code**

class Solution {
        
        List<List<String>> res = new ArrayList<>();
        List<String> path = new ArrayList<>();
        int n;
        public List<List<String>> partition(String s) {
        
            n = s.length();
            dfs(s,0);
            return res;
        }
        public void dfs(String s, int startIndex){
        
            if(startIndex==n){
        
                res.add(new ArrayList(path));
                return ;
            }
            //从startIndex开始枚举
            for(int i = startIndex; i<n; i++){
        
                if(is_huiwen(s.substring(startIndex,i+1))){
        
                    path.add(s.substring(startIndex,i+1));
                    dfs(s,i+1);
                    path.remove(path.size()-1);
                }
            }
        }
        public boolean is_huiwen(String s){
        
            char[] cs = s.toCharArray();
            int l = 0,r = cs.length - 1;
            while(l<r){
        
                if(cs[l]!=cs[r]){
        
                    return false;
                }else{
        
                    l++;
                    r--;
                }
            }
            return true;
        }
    }

#### 8. 复原IP地址 ####

题目链接：[93. 复原 IP 地址 - 力扣（LeetCode）][93. _ IP _ - _LeetCode]

思路：IP地址由4个分段组成，每一个分段的范围在`0~255`，每一段都有三次机会，选`1/2/3`个，我们可以通过枚举每一段的数字是否符合IP的规定，判断能否构成IP地址或者是否合理。

*  递归参数

public void dfs(String s,int num){
        
     }

*  递归终止条件

if(num==4 && s.length()==0){
        
                res.add(path.toString());
                return ;
            }
        //剪枝
           if(num>4){
        
                return;
            }

*  单层搜索的逻辑

for(int i=0;i<s.length()&&i<3;i++){
        
            if(i !=0 && s.charAt(0)=='0'){
        
                break;
            }
            String tmp = s.substring(0,i+1);
            if(Integer.valueOf(tmp)<=255){
        
                if(path.length()!=0){
        
                    tmp = "." + tmp;
                }
                path.append(tmp);
                dfs(s.substring(i+1),num + 1);
                path.delete(path.length() - tmp.length(), path.length());
            }

![image-20221122132612452][]

**Code**

class Solution {
        
        List<String> res = new ArrayList<>();
        StringBuilder path = new StringBuilder();
        public List<String> restoreIpAddresses(String s) {
        
            dfs(s,0);
            return res;
        }
        public void dfs(String s,int num){
        
            if(num==4 && s.length()==0){
        
                res.add(path.toString());
                return ;
            }
        //剪枝
           if(num>4){
        
                return;
            }
        for(int i=0;i<s.length()&&i<3;i++){
        
            if(i !=0 && s.charAt(0)=='0'){
        
                break;
            }
            String tmp = s.substring(0,i+1);
            if(Integer.valueOf(tmp)<=255){
        
                if(path.length()!=0){
        
                    tmp = "." + tmp;
                }
                path.append(tmp);
                dfs(s.substring(i+1),num + 1);
                path.delete(path.length() - tmp.length(), path.length());
            }
        }
      }
    }

### 子集问题 ###

##### 9. 子集I #####

题目链接：[78. 子集 - 力扣（LeetCode）][78. _ - _LeetCode]

**思路**：遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合

![image-20221122141827600][]

**回溯三部曲**

*  递归函数参数

public void dfs(int[]nums, int startIndex){
        
     }

*  递归终止条件

if(startIndex==nums.length){
        
                return ;
            }

*  单层搜索逻辑

for(int i = startIndex;i<nums.length;i++){
        
                path.add(nums[i]);
                dfs(nums,i+1);
                path.removeLast();
            }

**Code**

class Solution {
        
       List<List<Integer>> res = new ArrayList<>();
       LinkedList<Integer> path = new LinkedList<>();
       public List<List<Integer>> subsets(int[] nums) {
        
           dfs(nums,0);
           return res;
       }
       public void dfs(int[]nums, int startIndex){
        
           res.add(new ArrayList<>(path));
           if(startIndex==nums.length){
        
               return ;
           }
           for(int i = startIndex;i<nums.length;i++){
        
               path.add(nums[i]);
               dfs(nums,i+1);
               path.removeLast();
           }
       }
    }

##### 10.子集II #####

[力扣题目链接][Link 1]

**思路**：

*  数层需要去重，树枝不需要去重

![image-20221122145640974][]

**Code**

class Solution {
        
        List<List<Integer>> res = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        public List<List<Integer>> subsetsWithDup(int[] nums) {
        
            Arrays.sort(nums);
            dfs(nums,0);
            return res;
        }
        public void dfs(int[]nums,int start){
        
            res.add(new ArrayList<>(path));
            for(int i = start;i<nums.length;i++){
        
                if(i > start&&nums[i-1]==nums[i]){
        
                    continue;
                }
                path.add(nums[i]);
                dfs(nums,i+1);
                path.removeLast();
            }
    
        }
    }

[131. _ - _LeetCode]: https://leetcode.cn/problems/palindrome-partitioning/
[image-20221122092926063]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/c7f94c3c228544818f989b1129f909d6.png
[93. _ IP _ - _LeetCode]: https://leetcode.cn/problems/restore-ip-addresses/
[image-20221122132612452]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/5f51070f4fc341b19a21394151e685d3.png
[78. _ - _LeetCode]: https://leetcode.cn/problems/subsets/
[image-20221122141827600]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/0894151ec88446a9aba7a3306e9a6729.png
[Link 1]: https://leetcode.cn/problems/subsets-ii/
[image-20221122145640974]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/a2383bee97024252b8e17d80052ff96a.png