刷题-回溯

回溯的题，这类题老是忘

1. 虽然不是回溯，力扣1091

   最短、最优解这些用广度优先搜索，找到所有解的两个都行，但一般还是深度优先搜索更好写。

2. 深度优先搜索

   力扣695， 200， 547， 130

3. 回溯

   力扣17， 93， 79， 257，46，47，77，39，216，78，90，131

   93题：复原IP地址

   class Solution {
       public List<String> restoreIpAddresses(String s) {
           List<String> list = new ArrayList<>();
           if(s.length() < 4){
               return list;
           }
           backtrack(s, new StringBuilder(), 0, list);
           return list;
       }
   
       private void backtrack(String s, StringBuilder prefix, int num, List<String> list){
           if(num == 4 || s.length() == 0){
               if(num == 4 && s.length() == 0){
                   list.add(prefix.toString());
               }
               return;
           }
           int n = s.length();
           for(int i=0; i<n && i<=2; ++i){
               if(i != 0 && s.charAt(0) == '0'){
                   return;
               }
               String curr = s.substring(0, i+1);
               if(Integer.valueOf(curr) <= 255){
                   if(num != 0){
                       curr = "." + curr;
                   }
                   prefix.append(curr);
                   backtrack(s.substring(i+1), prefix, num+1, list);
                   prefix.delete(prefix.length()-curr.length(), prefix.length());
               }
           }
       }
   }

   力扣257

   class Solution {
       public List<String> binaryTreePaths(TreeNode root) {
           List<String> list = new ArrayList<>();
           dfs(root, new StringBuilder(), list);
           return list;
       }
   
       private void dfs(TreeNode root, StringBuilder path, List<String> list){
           path.append(root.val + "");
           if(root.left == null && root.right == null){
               list.add(path.toString());
               return;
           }
           if(root.left != null){
               dfs(root.left, new StringBuilder(path).append("->"), list);
           }
           if(root.right != null){
               dfs(root.right, new StringBuilder(path).append("->"), list);
           }
       }
   }

   力扣47

   for(int i=0; i<n; ++i){
                  if(!isVisited[i]){
                      isVisited[i] = true;
                      path.add(nums[i]);
                      backtrack(nums, list, path, isVisited);
                      path.remove(path.size()-1);
                      isVisited[i] = false;
                      //111123, 回溯后，跳到最后一个1，for循环那还有一个++i，从2开始
                      while(i < n-1 && nums[i] == nums[i+1]){
                          ++i;
                      }
                  }
              }

• 有顺序的，排列：for循环从0开始
• 没顺序的，组合：for循环从start开始，传参

​ 力扣131

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> list = new ArrayList<>();
        List<String> path = new ArrayList<>();
        backtrack(s, list, path);
        return list;
    }

    private void backtrack(String s, List<List<String>> list, List<String> path){
        if(s.length() == 0){
            list.add(new ArrayList<>(path));
            return;
        }
        int n = s.length();
        for(int i=0; i<n; ++i){
            if(check(s, i)){
                path.add(s.substring(0, i+1));
                backtrack(s.substring(i+1), list, path);
                path.remove(path.size()-1);
            }
        }
    }

    private boolean check(String s, int k){
        int i = 0, j = k;
        while(i < j){
            if(s.charAt(i++) != s.charAt(j--)){
                return false;
            }
        }
        return true;
    }
}