回溯专题——day35

---

分割问题

7. 分割回文串

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

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

回溯三部曲

• 递归函数参数

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

• 递归函数终止条件

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

• 单层搜索的逻辑

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);
1
2
3
4
5

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;
    }
}
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

8. 复原IP地址

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

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

• 递归参数

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

• 递归终止条件

   if(num==4 && s.length()==0){
            res.add(path.toString());
            return ;
        }
    //剪枝
       if(num>4){
            return;
        }
1
2
3
4
5
6
7
8

• 单层搜索的逻辑

 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());
        }
1
2
3
4
5
6
7
8
9
10
11
12
13

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());
        }
    }
  }
}
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

子集问题

9. 子集I

题目链接：78. 子集 - 力扣（LeetCode）

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

回溯三部曲

• 递归函数参数

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

• 递归终止条件

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

• 单层搜索逻辑

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

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();
       }
   }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

10.子集II

力扣题目链接

思路：

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

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();
        }

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