有几个需要注意的要点：

  1. // 需要new一个新的对象，不可以直接写成res.add(sub);
  2. res.add(new ArrayList<>(sub));
  4. // 如果是回溯算法，记得撤销动作，如果是基本类型的修改不用撤销
  5. sub.remove(sub.size()-1);

经典回溯：

46. 全排列

46. 全排列
image.png

  1. class Solution {
  3.     public List<List<Integer>> permute(int[] nums) {
  4.       int n=nums.length;
  5.       boolean[] used=new boolean[n];
  6.       List<Integer> path=new ArrayList<>();
  7.       List<List<Integer>> res=new ArrayList<>();
  8.       backtrack(nums,path,used,res);
  9.       return res;
  10.     }
  12.     private void backtrack(int[] nums,List<Integer> path,boolean[] used,List<List<Integer>> res){
  13.       if(path.size()==nums.length){
  14.         res.add(new ArrayList<>(path));
  15.         return;
  16.       }
  17.       for(int i=0;i<nums.length;i++){
  18.         if(!used[i]){
  19.           path.add(nums[i]);
  20.           used[i]=true;
  21.           backtrack(nums,path,used,res);
  22.           used[i]=false;
  23.           path.remove(path.size()-1);
  24.         }
  25.       }
  26.     }
  27. }

剑指 Offer 38. 字符串的排列

剑指 Offer 38. 字符串的排列
和上面的全排列非常相似，区别：这道题input中用来排列的元素可能重复
image.png
题目中给的abc是没有重复字母的，乍一看和上面一题一模一样，但是，第一次提交后发现，输入是”aab”时，重复的a会导致有重复的排列。需要去重。
去重的方法：

  1. 排序，把相同的字符都放在一起

  2. 在backtrack函数中，if(i>0&&array[i]==array[i-1]&&!used[i-1]) continue; 如果当前元素和前一个元素相同，且前一个元素没有被用到，那么跳过。（如果前一个a没有被用到现在的组合中，而使用了现在这个a，那就和使用了前一个a没用现在这个a的排列重复了）

    1. class Solution {
    2.  public String[] permutation(String s) {
    3.    char[] array=s.toCharArray();
    4.    List<String> resList=new ArrayList<>();
    5.    StringBuilder sb=new StringBuilder();
    6.    boolean[] used=new boolean[array.length];
    7.    Arrays.sort(array);
    8.    backtrack(sb,resList,array,used);
    9.    String[] result = resList.toArray(new String[resList.size()]);
    10.    return result;
    11.  }
    13.  private void backtrack(StringBuilder sb,List<String> resList,char[] array,boolean[] used){
    14.    if(sb.length()==array.length){
    15.      resList.add(sb.toString());
    16.      return;
    17.    }
    18.    for(int i=0;i<array.length;i++){
    19.      if(used[i]) continue;
    20.      if(i>0&&array[i]==array[i-1]&&!used[i-1]) continue;
    21.      sb.append(array[i]);
    22.      used[i]=true;
    23.      backtrack(sb,resList,array,used);
    24.      used[i]=false;
    25.      sb.deleteCharAt(sb.length()-1);
    26.    }
    27.  }
    28. }

    131. 分割回文串

    题目链接：131. 分割回文串
    Screenshot_20210610_002532.jpg

    1. class Solution {
    2.  public List<List<String>> partition(String s) {
    3.    List<List<String>> res=new ArrayList<>();
    4.    ArrayList<String> sub=new ArrayList<>();
    5.    dfs(s,0,sub,res);
    6.    return res;
    7.  }
    9.  private void dfs(String s,int start,ArrayList<String> sub,List<List<String>> res){
    10.    if(start==s.length()){
    11.      res.add(new ArrayList<>(sub));
    12.      return;
    13.    }
    14.    for(int i=start;i<s.length();i++){
    15.      String s1=s.substring(start,i+1);
    16.      if(!isPalindrome(s1)) continue;
    17.      sub.add(s1);
    18.      dfs(s,i+1,sub,res);
    19.      sub.remove(sub.size()-1);
    20.    }
    21.  }
    23.  private boolean isPalindrome(String s){
    24.    if(s==null||s.length()<2) return true;
    25.    int l=0,r=s.length()-1;
    26.    while(l<r){
    27.      if(s.charAt(l++)!=s.charAt(r--)){
    28.        return false;
    29.      }
    30.    }
    31.    return true;
    32.  }
    33. }

    用dp来记录，进一步提高效率（提高了一点点点）

    1. class Solution {
    2.  public List<List<String>> partition(String s) {
    3.    List<List<String>> res=new ArrayList<>();
    4.    ArrayList<String> sub=new ArrayList<>();
    5.    int len=s.length();
    6.    boolean[][] dp=new boolean[len][len];
    7.    for(int i=0;i<len;i++){
    8.      isPalindrome(s,i,i,dp);
    9.      isPalindrome(s,i,i+1,dp);
    10.    }
    11.    dfs(s,0,sub,res,dp);
    12.    return res;
    13.  }
    15.  private void dfs(String s,int start,ArrayList<String> sub,List<List<String>> res,boolean[][] dp){
    16.    if(start==s.length()){
    17.      res.add(new ArrayList<>(sub));
    18.      return;
    19.    }
    20.    for(int i=start;i<s.length();i++){
    21.      if(!dp[start][i]) continue;
    22.      sub.add(s.substring(start,i+1));
    23.      dfs(s,i+1,sub,res,dp);
    24.      sub.remove(sub.size()-1);
    25.    }
    26.  }
    28.  private void isPalindrome(String s,int i,int j,boolean[][] dp){
    29.    int len=s.length();
    30.    while(i>=0&&j<len&&s.charAt(i)==s.charAt(j)){
    31.      dp[i][j]=true;
    32.      i--;
    33.      j++;
    34.    }
    35.  }
    36. }

    有一道困难题，看起来和这个很类似，但其实不能用相同方法来解决，会超时。

    132. 分割回文串 II 困难

    132. 分割回文串 II
    使用动态规划，dp[i]表示s.substring(0,i)需要最少切割几次

    1. class Solution {
    2.  public int minCut(String s) {
    3.      if(s == null || s.length() <= 1)
    4.          return 0;
    5.      int len = s.length();
    6.      int dp[] = new int[len];
    7.      Arrays.fill(dp, len-1);
    8.      for(int i = 0; i < len; i++){
    9.          findMinCut(s , i , i , dp);  // 奇数回文串以1个字符为中心
    10.          findMinCut(s, i , i+1 , dp); // 偶数回文串以2个字符为中心
    11.      }
    12.      return dp[len-1];
    13.  }
    14.  private void findMinCut(String s, int i, int j, int[] dp){
    15.      int len = s.length();
    16.      while(i >= 0 && j < len && s.charAt(i) == s.charAt(j)){
    17.          //以当前字符为中心的最大回文串左侧为i，右侧为j，那s[i]~s[j]长度是不需要切割的
    18.          //只需要在s[i-1]处切一刀即可，即dp[i-1]+1。所以更新dp[j] = min(dp[j] , dp[i-1]+1)
    19.          dp[j] = Math.min(dp[j] , (i==0?-1:dp[i-1])+1);
    20.          i--;
    21.          j++;
    22.      }
    23.  }
    24. }

93. 复原 IP 地址

题目：93. 复原 IP 地址
image.png
这个答案的效率不太好，但是是我自己想出来的，所以记录一下思路
有几个要点：
（1）当前的数字最短能有多短
比如：输入的数据为“25525511135”，一共是11位，在不知道具体数字的情况下，我们也能知道，最短可以是2位，如果4个数字中有一个是1位，那么就会出现数字多余的情况。
（2）当前的数字最长能有多长
比如：输入的数据为“1111”，一共是11位，在不知道具体数字的情况下，我们也能知道，最长只可以是1位，如果4个数字中有一个是2位，那么就会出现数字不够用的情况。
（3）转换成数字之前的格式校验
当时没注意到这一点，导致漏了很多0
比如”01”这个字符串是不符合要求的，虽然转换成int之后是1。转换之前需要进行校验。
（4）把结果加入resList的方法
一开始path我是用的List类型，把每个位置的数字存起来然后用下面这种愚蠢的办法进行拼接。之后看了大佬的答案，首先做了改进resList.add(String.join(“.”, path));

  1.       if(nums.size()==4){
  2.         String str=nums.get(0)+"."+nums.get(1)+"."+nums.get(2)+"."+nums.get(3);
  3.         resList.add(str);
  4.         return;
  5.       }

可以看到优化了很多很多
image.png

  1. class Solution {
  2.     public List<String> restoreIpAddresses(String s) {
  3.       int len=s.length();
  4.       if(len>12||len<4) return new ArrayList<>();
  5.       List<String> resList=new ArrayList<>();
  6.       List<String> path=new ArrayList<>();
  7.       dfs(0,path,resList,s);
  8.       return resList;
  9.     }
  11.     private void dfs(int start,List<String> path,List<String> resList,String s){
  12.       if(path.size()==4){
  13.         resList.add(String.join(".", path)); //优化了很多！！！
  14.         return;
  15.       }
  16.       int len=minLen(start,path,s);
  17.       int limit=maxLen(start, path, s);
  18.       for(;len<=limit&&(start+len)<=s.length();len++){
  19.         String str=s.substring(start,start+len);
  20.         if(str.length()>1&&str.charAt(0)=='0') continue;
  21.         int num=Integer.parseInt(str);
  22.         if(num>=0&&num<=255){
  23.           path.add(str);
  24.           dfs(start+len,path,resList,s);
  25.           path.remove(path.size()-1);
  26.         }
  27.       }
  28.     }
  30.     private int minLen(int start,List<String> path,String s){
  31.       int used=path.size();
  32.       int remainNumber=s.length()-start;
  33.       int remainPos=4-used;
  34.       if((remainNumber/3)==(remainPos-1)){
  35.         return remainNumber%3==0?1:remainNumber%3;
  36.       }else if((remainNumber/3)==remainPos){
  37.         return 3;
  38.       }else{
  39.         return 1;
  40.       }
  41.     }
  43.     private int maxLen(int start,List<String> path,String s){
  44.       int used=path.size();
  45.       int remainNumber=s.length()-start;
  46.       int remainPos=4-used;
  47.       int len=remainNumber-remainPos+1;
  48.       return Math.min(3,len);
  49.     }
  50. }

大佬的思路：
代码更简洁，但是效率没提升

  1. class Solution {
  2.     public List<String> restoreIpAddresses(String s) {
  3.       int len=s.length();
  4.       if(len>12||len<4) return new ArrayList<>();
  5.       List<String> resList=new ArrayList<>();
  6.       List<String> path=new ArrayList<>();
  7.       dfs(0,path,resList,s);
  8.       return resList;
  9.     }
  11.     private void dfs(int start,List<String> path,List<String> resList,String s){
  12.       if(path.size()==4){
  13.         resList.add(String.join(".", path));
  14.         return;
  15.       }
  16.       for(int len=1;len<=3&&(start+len)<=s.length();len++){
  17.         String str=s.substring(start,start+len);
  18.         if(str.length()>1&&str.charAt(0)=='0') continue;
  19.           //不够了或有多余的
  20.           //int remainNumber=s.length()-start-len;
  21.           //int remainPos=4-path.size()-1;
  22.         if((s.length()-start-len)<(3-path.size())||(s.length()-start-len)>(3-path.size())*3) continue;
  23.         int num=Integer.parseInt(str);
  24.         if(num>=0&&num<=255){
  25.           path.add(str);
  26.           dfs(start+len,path,resList,s);
  27.           path.remove(path.size()-1);
  28.         }
  29.       }
  30.     }
  31. }

剑指 Offer 12. 矩阵中的路径

链接：剑指 Offer 12. 矩阵中的路径
写的有点丑陋

  1. class Solution {
  2.     int m,n;
  3.     char[] c;
  4.     boolean[][] visited;
  5.     char[][] board;
  6.     int[][] directions=new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
  8.     public boolean exist(char[][] board, String word) {
  9.         this.board=board;
  10.         m=board.length;
  11.         n=board[0].length;
  12.         c=word.toCharArray();
  13.         visited=new boolean[m][n];
  15.         for(int i=0;i<m;i++){
  16.             for(int j=0;j<n;j++){
  17.                 if(board[i][j]==c[0]){
  18.                     visited[i][j]=true;
  19.                     if(backtrack(i,j,1)) return true;
  20.                     visited[i][j]=false;;
  21.                 }
  22.             }
  23.         }
  24.         return false;
  25.     }
  27.     private boolean backtrack(int i,int j,int next){
  28.         if(next==c.length) return true;
  29.         for(int[] dir:directions){
  30.             int x=i+dir[0];
  31.             int y=j+dir[1];
  32.             if(x>=0&&y>=0&&x<m&&y<n&&c[next]==board[x][y]&&!visited[x][y]){
  33.                 visited[x][y]=true;
  34.                 if(backtrack(x, y, next+1)) return true;
  35.                 visited[x][y]=false;
  36.             }
  37.         }        
  38.         return false;
  39.     }
  40. }