回溯

1.基础知识

解决一个回溯问题，实际上就是一个决策树的遍历过程，只需要思考三个问题：

路径：也就是已经做出的选择
选择列表：也就是当前可以做的选择
结束条件：就是达到决策树底部，无法再进行选择的条件

回溯算法的框架
```
List<String> result=new ArrayList<>();
public void backtrack(路径,选择列表){
    if(满足结束条件){
        result.add(路径)
    	return;
    }
    while(选择在选择列表){
        做选择；
        backtrack(路径，选择列表)；
        撤销选择；
    }
}
```
其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」

2.相关题目

2.1 所有子集

给定一个整数数组 nums ，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。你可以按任意顺序返回解集。
```
  输入：nums = [1,2,3]
  输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
```

首先就是找出结束条件，因为是要找出所有的子集，所以我们只要路径中的元素不为零就可以添加路径，但此时我们不能return，因为还没有结束

  if(path.size()>0){
    ans.add(new ArrayList<>(path));
  }

选择列表就是数组nums,相应的做选择就是path.add(nums[i]),撤销选择就是path.removeLast()

  class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
        ans.add(new ArrayList<>());
        dfs(nums,0);

        return ans;
    }
    public void dfs(int[] nums, int start){
        if(path.size()>0){
            ans.add(new ArrayList<>(path));

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

注意这里我们需要在dfs传入一个start参数，不然我们在选择同一个路径的时候会多次选择同一个nums[i]

2.2 生成匹配的括号

正整数 n 代表生成括号的对数，请设计一个函数，用于能够生成所有可能的并且有效的括号组合。

class Solution {
    List<String> ans = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        dfs(n, 0, new StringBuilder(), 0, n);
        return ans;
    }
    // open代表的是左括号数量,close右括号数量,当左括号数量小于n的时候可以继续增加左括号，当发现右括号小于左括号数量的时候们可以继续添加右括号，因为执行的顺序是先添加左括号再添加右括号，所以括号总是匹配的
    public void dfs(int n, int open, StringBuilder cur, int close, int max){
        if(cur.length() == max * 2){
            ans.add(cur.toString());
            return ;
        }
        if(open < max){
            cur.append("(");
            dfs(n, open + 1, cur, close, max);
            cur.deleteCharAt(cur.length() - 1);
        }
        if(close < open){
            cur.append(")");
            dfs(n, open, cur, close + 1, max);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}

2.3 生成回文子串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。回文串是正着读和反着读都一样的字符串。输入：s = “aab” 输出：[[“a”,”a”,”b”],[“aa”,”b”]]

此题可以从0开始，判断包含索引0的字符是否能够组成回文串，之后往后移，利用start来标识开始位置

class Solution {
    List<List<String>> ans = new ArrayList<>();
    Deque<String> path = new LinkedList<>();
    public List<List<String>> partition(String s) {
        dfs(s,0);
        return ans;
    }
    public void dfs(String s,int start){
      //结束条件
        if(start>=s.length()){
            ans.add(new ArrayList<>(path));
        }
        for(int i=start;i<s.length();i++){
            if(isPalindrome(s.substring(start,i+1))) {
                path.addLast(s.substring(start,i+1));
            }
            else continue;
            dfs(s,i+1);
            path.removeLast();
        }
    }
    //双指针判断是否回文子串
    public boolean isPalindrome(String s){
        int i = 0;
        int j = s.length()-1;
        while(i<j){
            if(s.charAt(i++)!=s.charAt(j--)) return false;            
        }
        return true;
    }
}

2.4 复原IP

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能从 s 获得的有效 IP 地址。你可以按任何顺序返回答案。

有效 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

例如：”0.1.2.201” 和 “192.168.1.1” 是有效 IP 地址，但是 “0.011.255.245”、”192.168.1.312” 和 “192.168@1.1” 是无效 IP 地址。

首先我们需要一个判断是否是合理IP的函数，有两个方面，不能以0开头，每段数字要在0-255之间

public boolean isValidIp(String s){
       String[] str = s.split("\\.");
       for(String tmp:str){
          // if(tmp.length() == 0) return false;
           if(tmp.charAt(0) == '0'&&tmp.length()>1) return false;
           if(Integer.valueOf(tmp) > 255) return false;
       }
       return true;
   }

其次，我们需要枚举可能出现的情况，根据“.”出现的位置进行枚举，结束的条件就是我们新构造的字符串的长度 = 给定字符串长度 + 3

public void dfs(String s, int idx, StringBuilder sb){
       if(sb.length() == s.length() + 3){
            if(isValidIp(sb.toString())){
                ans.add(sb.toString());
            }
            return ;
       }
       for(int i = idx; i < sb.length(); i ++){
           sb.insert(i,".");
           dfs(s, i + 2 , sb);
           sb.deleteCharAt(i);
       }
   }

完整答案

class Solution {
    List<String> ans = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        if(s.length() > 12) return new ArrayList<>();
        StringBuilder sb = new StringBuilder(s);
        dfs(s, 1, sb);
        return ans;
    }
    public void dfs(String s, int idx, StringBuilder sb){
        if(sb.length() == s.length() + 3){
             if(isValidIp(sb.toString())){
                 ans.add(sb.toString());
             }
             return ;
        }
        //这里注意，i要小于我们构造字符串的长度，而不是给定的字符串s的长度
        for(int i = idx; i < sb.length(); i ++){
            sb.insert(i,".");
            dfs(s, i + 2 , sb);
            sb.deleteCharAt(i);
        }
    }
    public boolean isValidIp(String s){
        String[] str = s.split("\\.");
        for(String tmp:str){
           // if(tmp.length() == 0) return false;
            if(tmp.charAt(0) == '0'&&tmp.length()>1) return false;
            if(Integer.valueOf(tmp) > 255) return false;
        }
        return true;
    }
}

2.5 含有k个元素的组合

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。组合问题：结束条件为路径的大小等于k 此中没有重复元素

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        dfs(n,1,k);
        return ans;
    }
    public void dfs(int n, int start,int k){
        if(path.size()==k){
            ans.add(new ArrayList<>(path));
            return ;
        }
        for(int i=start;i<=n;i++){
            path.add(i);
            dfs(n,i+1,k);
            path.removeLast();
        }
    }
}

2.6 允许选择重复元素的组合

给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合。candidates 中的数字可以无限制重复被选取。如果至少一个所选数字数量不同，则两种组合是不同的。输入: candidates = [2,3,6,7], target = 7 输出: [[7],[2,2,3]] 对于给定的输入，保证和为 target 的唯一组合数少于 150 个。允许选择重复元素，那么在做选择递归的时候不需要一个start，即选择了当前元素，下一个元素还可以选择当前元素。如果不允许选择重复元素，那么直接令start = i + 1就行

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(candidates,0,target);
        return ans;
    }
    public void dfs(int[] candidates, int sum, int target){
        if(sum > target) return ;
        if(sum == target){
            ans.add(new ArrayList<>(path));
            return ;
        }
        for(int i = 0; i < candidates.length; i++){
            path.add(candidates[i]);
            sum += candidates[i];
            dfs(candidates,sum, target);
            path.removeLast();
            sum -= candidates[i];
        }
    }
}

2.7 含有重复元素的组合

给定一个可能有重复数字的整数数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次，解集不能包含重复的组合。输入: candidates = [10,1,2,7,6,1,5], target = 8, 输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ] 这个题目和上一个题目的区别在于数组中有重复数字，但是当前数字不可重复选取，而且解集不能包含重复组合这里我们先对数组进行排序，直接回溯，和之前一样，我们所需要做的就是去重，首先想到的是利用哈希表，但是时间复杂度太高，这里我们可以用一个条件

if(i > start && candidates[i] == candidates[i-1]) continue;

便可以实现去重操作

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

2.8 全排列

给定一个不含重复数字的整数数组 nums ，返回其所有可能的全排列。可以按任意顺序返回答案排列问题：需要保证所有元素都出现，但一个元素用过之后，这个序列就不能再用这个元素，利用布尔数组解决这个问题

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> permute(int[] nums) {
        boolean[] used = new boolean[nums.length];
        dfs(nums,used);
        return ans;
    }
    public void dfs(int[] nums, boolean[] used){
        if(path.size() == nums.length){
            ans.add(new ArrayList<>(path));
            return ;
        }
        for(int i = 0; i < nums.length; i++){
           if(!used[i]){
                path.add(nums[i]);
                used[i] = true;
                dfs(nums, used);
                path.removeLast();
                used[i] = false;
           }
        }
    }
}

2.9 含有重复元素的全排列

给定一个可包含重复数字的整数集合 nums ，按任意顺序返回它所有不重复的全排列。这个问题跟上面题目多了个一个条件：nums中包含重复元素，这样在我们回溯的过程中可能出现相同排列如果直接利用i != 0 && nums[i] == nums[i - 1] continue就跳过的话可能会跳过本不应该跳过的例如：[1,1,2]，遍历完第一个1之后，第二个1满足nums[i] == nums[i - 1]，因此也被跳过了，那么答案就错了。所以只要知道何时重复数字不应跳过，本题就搞定了。遍历完第一个1之后，（i=0时）第一个1标记了visited，（i=1时）第二个1还没被遍历，因此仍为false，此时就不应该跳过这个重复数字，即visited[i - 1] == true时不应跳过，因此才有的这个条件： if(used[i]||i != 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        boolean[] used = new boolean[nums.length];
        dfs(nums,used);
        return ans;
    }
    public void dfs(int[] nums, boolean[] used){
        if(path.size() == nums.length){
            ans.add(new ArrayList<>(path));
            return ;
        }

        for(int i=0;i<nums.length;i++){
            if(used[i]||i != 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
            path.add(nums[i]);
            used[i] = true;
            dfs(nums,used);
            path.removeLast();
            used[i] = false;
        }
    }
}

回溯