for循环横向遍历，递归纵向遍历，回溯不断调整结果集
画树，回溯要画树

77. 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。

result.add(new ArrayList(path))：开辟一个独立地址，地址中存放的内容为path链表，后续path的变化不会影响到res

res.add(path)：将res尾部指向了path地址，后续path内容的变化会导致res的变化。

class Solution {
    LinkedList<Integer> path = new LinkedList<>();
    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {
        backTracking(n,k,1);
        return result;
    }

    void backTracking(int n, int k, int startIndex){
        if(path.size()==k){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i <= n; i++) {
            path.add(i);
            backTracking(n,k,i+1);
            path.removeLast();//回溯
        }
    }
}

剪枝操作优化代码：

for (int i = startIndex; i <= n; i++) {

剪枝：

for (int i = startIndex; i <=n-(k-path.size())+1; i++) {

path.size() 是当前路径里元素的个数
k-path.size() 是还需要的元素个数
n-(k-path.size())+1 至多走到哪里

216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字 最多使用一次 
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

• 这题和上面一题十分相似，就浅浅改了一下上面的代码

class Solution {

     LinkedList<Integer> path = new LinkedList<>();
     List<List<Integer>> result = new ArrayList<>();

    public  List<List<Integer>> combinationSum3(int k, int n) {
        if(k > n){//如果n小于k的话直接返回
            return result;
        }
        backTracking(k,n,1);
        return result;
    }

     void backTracking(int k, int n, int startIndex){

        if(path.size()==k){//数组的长度达到标准之后
            int sum = 0;
            for (Integer p : path) {
                sum +=p;
            }
            if(sum == n){//看数组中数字之和是否达到标准
                result.add(new ArrayList<>(path));
            }
            return;
        }
        for (int i = startIndex; i <= n; i++) {
            path.add(i);
            backTracking(k,n,i+1);
            path.removeLast();
        }
    }
}

• 结果超出时间限制，因为没有剪枝

for (int i = startIndex; i <= Math.min(n-(k*(k-1)/2),9) ; i++) {

• k*(k-1)/2 是对前k-1个数的求和
• n-(k*(k-1)/2) 和 9 取最小是怕n太大，k太小导致path里的数 > 9
  
  
  

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

• 把按键上对应的数字转换成字符串letters，遍历的时候要遍历的是字符串

class Solution {

     List<String> result = new ArrayList<>();
    static String[] letters = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};//下标就是按键上的数字

    public List<String> letterCombinations(String digits) {
        if(digits.equals(""))
             return result;//对特殊情况特殊处理
        backTracking(digits,0);//从零开始
        return result;
    }

    static StringBuilder sb = new StringBuilder();
    
     void backTracking(String digits, int index){
         //index指的是当前对哪个数字进行处理
         if(sb.length()==digits.length()){
            result.add(sb.toString());
            return;
         }
        String letter = letters[(digits.charAt(index))-'0'];//取当前下标对应的字符串
        for (int i = 0; i < letter.length(); i++) {
            sb.append(letter.charAt(i));
            backTracking(digits,index+1);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}

• 感觉慢慢理解回溯了?
  
  
  

39. 组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

• 对组合问题的变形：允许元素重复使用，不固定路径数组的长度

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        
        combine(candidates, target, 0);
        return res;
    }

    void combine(int[] candidates, int target, int startIndex){
        int sum = 0;
        //算出当前路径的结点之和
        for (Integer node : path) {
            sum += node;
        }
        if(sum == target){
            res.add(new ArrayList<>(path));//得到符合条件的结果，把路径加到结果集中
            return;
        }
        if(sum > target){
            return;//当前路径上的结点之和已经大于所求，不用再往下加了
        }
        for (int i = startIndex; i < candidates.length; i++) {
            path.add(candidates[i]);//把当前的元素加入path中
            combine(candidates,target,i);
            path.remove(path.size()-1);
        }
    }
}

40. 组合总和 II

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。

• 本题也是对组合问题的变形：candidates中的元素 无序 且 重复
• 元素无序 给剪枝操作增加了难度，我在操作前对数组candidates进行了排序
• 元素重复 我的做法是对结果集res 新建了一个result进行去重，但是有的测试用例超时

class Solution {
   List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);//先给数组排序
        int length = candidates.length;
        for (int candidate : candidates) {
            if(candidate > target){
                length--;
            }
        }
        Arrays.copyOf(candidates,length);
        combine(candidates, target, 0);
        //此时已经拿到结果集res,但是需要对其进行去重操作
        List<List<Integer>> result = new ArrayList<>();
        for (List<Integer> re : res) {
            if (!result.contains(re)){
                result.add(re);//如果真正的结果集result中不包括re，就可以把re加入道result
            }
        }
        return result;
    }

    void combine(int[] candidates, int target, int startIndex){
        int sum = 0;
        //算出当前路径的结点之和
        for (Integer node : path) {
            sum += node;
        }
        if(sum == target){
            res.add(new ArrayList<>(path));//得到符合条件的结果，把路径加到结果集中
            return;
        }
        if(sum > target){
            return;//当前路径上的结点之和已经大于所求，不用再往下加了
        }
        for (int i = startIndex; i < candidates.length; i++) {
            path.add(candidates[i]);//把当前的元素加入path中
            combine(candidates,target,i+1);
            path.remove(path.size()-1);
        }
    }
}

• 就是这个用例超时，仔细瞅瞅这个用例，它说要对重复的数据进行处理，而不能只改结果集。确实，那样效率太低了?

[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
30

• 我在for循环中加入了如下语句，想使重复的元素跳出当前循环

if(i>0&&candidates[i]==candidates[i-1]){
     continue;
}

• 但是他把满足条件的含有重复元素的结果也给剪掉了，是剪枝的条件出了问题
  
• 把 i>0 换成 i>startIndex 后运行通过

if(i>startIndex&&candidates[i]==candidates[i-1]){

131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。

• 这题是分割问题，但是本质和组合问题思路一样
• 剪枝的思路是：如果当前切出来的子串已经不是回文串了，就continue进入下一次循环，这样可以保证叶子结点都是满足要求的path
  

class Solution {
    List<List<String>> res = new ArrayList<>();
    LinkedList<String> path = new LinkedList<>();

    public List<List<String>> partition(String s) {
        combine(s,0);
        return res;
    }

    void combine(String s, int startIndex){

        if(startIndex >= s.length()){
            res.add(new LinkedList<>(path));//收获叶子结点
        }
        
        for (int i = startIndex; i < s.length(); i++) {
            if (isPalindromes(s,startIndex,i)){
                path.add(s.substring(startIndex,i+1));//因为subString()方法是左闭右开的
            } else {
                continue;//如果当前的子串都不是回文串，已经不满足题意，不必再往下切了
            }
            combine(s,i+1);//再往树的下一层遍历
            path.removeLast();//回溯
        }
        
    }
    // 判断是否是回文子串
    boolean isPalindromes(String s, int startIndex, int endIndex){
        while (true){
            if(startIndex > endIndex){
                return true;
            }
            if(s.charAt(startIndex)==s.charAt(endIndex)){
                startIndex++;
                endIndex--;
            } else {
                return false;
            }
        }
    }
}

93. 复原 IP 地址

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

❗ ❗ ❗ 不是自己写出来的

• 按照自己本来的思路写，是new了一个StringBuilder，想着这样操作方便些，但是很难回溯啊，就把自己绕进去了，下面的题解是在String上用subString()的方法操作
• 还有递归出口，要专门创建一个int去记录逗点的数量

class Solution {

    List<String> result = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        if (s.length() > 12) return result; // 算是剪枝了
        backTrack(s, 0, 0);
        return result;
    }

    // startIndex: 搜索的起始位置， pointNum:添加逗点的数量
    private void backTrack(String s, int startIndex, int pointNum) {
        if (pointNum == 3) {// 逗点数量为3时，分隔结束
            // 判断第四段⼦字符串是否合法，如果合法就放进result中
            if (isValid(s,startIndex,s.length()-1)) {
                result.add(s);
            }
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            if (isValid(s, startIndex, i)) {
                s = s.substring(0, i + 1) + "." + s.substring(i + 1);//在str的后⾯插⼊⼀个逗点
                pointNum++;
                backTrack(s, i + 2, pointNum);// 插⼊逗点之后下⼀个⼦串的起始位置为i+2
                pointNum--;// 回溯
                s = s.substring(0, i + 1) + s.substring(i + 2);// 回溯掉刚刚插入的逗点
            } else {
                break;//这里用break而不是continue是因为如果当前情况就不符合条件，再往后遍历，数字只会越来越大，更不符合条件
            }
        }
    }

    // 判断字符串s在左闭⼜闭区间[start, end]所组成的数字是否合法
    private Boolean isValid(String s, int start, int end) {
        if (start > end) {
            return false;
        }
        if (s.charAt(start) == '0' && start != end) { // 0开头的数字不合法
            return false;
        }
        int num = 0;
        for (int i = start; i <= end; i++) {
            if (s.charAt(i) > '9' || s.charAt(i) < '0') { // 遇到⾮数字字符不合法
                return false;
            }
            num = num * 10 + (s.charAt(i) - '0');
            if (num > 255) { // 如果⼤于255了不合法
                return false;
            }
        }
        return true;
    }
}

• 回溯是把当前for循环里的操作给回溯掉，干干净净的进入下一个循环
• 感觉这一题是挺难的，现在还有点没迷过来?
  
  
  

78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

class Solution {
     LinkedList<Integer> path = new LinkedList<>();
     List<List<Integer>> res = new LinkedList<>();

    public  List<List<Integer>> subsets(int[] nums) {
        res.add(new LinkedList<>(path));//把空的path进去
        combine(nums,0);
        return res;
    }

     void combine(int[] nums, int startIndex){

        if(!path.isEmpty()&&path.getLast()==nums[nums.length-1]){
            return;//递归出口
        }

        for (int i = startIndex; i < nums.length; i++) {
            path.add(nums[i]);
            res.add(new LinkedList<>(path));//每一个结点都要收集
            combine(nums,i+1);
            path.removeLast();//回溯
        }
    }
}

• 这题比较简单，子集的特点就是每一个结点都要收集，那我们在添加路径时收集就可以了
• 递归的出口是当path最后一个数是数组中的最后一个数时，不再向下递归
  
  
  

90. 子集 II

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

• 这题和之前相比就多了一个去重操作，先排序后去重

class Solution {
     LinkedList<Integer> path = new LinkedList<>();
     List<List<Integer>> res = new LinkedList<>();

    public  List<List<Integer>> subsetsWithDup(int[] nums) {
        res.add(new LinkedList<>(path));//把空的path进去
        Arrays.sort(nums);//先排序
        combine(nums,0);
        return res;
    }

     void combine(int[] nums, int startIndex){
        for (int i = startIndex; i < nums.length; i++) {
            if (i > startIndex && nums[i] == nums[i - 1]) {
                continue;//去重
            }
            path.add(nums[i]);
            res.add(new LinkedList<>(path));//每一个结点都要收集
            combine(nums,i+1);
            path.removeLast();//回溯
        }
    }
}

491. 递增子序列

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

class Solution {

    List<List<Integer>> res = new ArrayList<>();
    ArrayList<Integer> path = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        combine(nums, 0);
        return res;
    }
    void combine(int[] nums, int startIndex) {
        if (path.size() > 1) {
            res.add(new ArrayList<>(path));
        }
        Map<Integer, Integer> map = new HashMap();//每层一个map
        for (int i = startIndex; i < nums.length; i++) {
            if (!path.isEmpty() && nums[i] < path.get(path.size() - 1)) {
                continue;//剪枝
            }
            if(map.getOrDefault(nums[i],0)>0){//如果该元素的value不是0，说明之前添加过，直接进下一次循环
                continue;//去重
            }
            map.put(nums[i],map.getOrDefault(nums[i],0)+1);//第一次遍历到该元素时，以数组元素为key，value赋1
            path.add(nums[i]);
            combine(nums, i + 1);
            path.remove(path.size() - 1);//回溯
        }
    }
}

• 这里去重是用map实现的

default V getOrDefault ​( Object key , V defaultValue ) 返回指定key映射到的value，如果当前map不包含当前key的映射，则返回 defaultValue 。

46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

• 全排列问题 还是要画树
  

• 循环遍历当前path中没有的数

List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {
        combine(nums);
        return res;
    }
    void combine(int[] nums){
        if (path.size()== nums.length){
            res.add(new ArrayList<>(path));//收集结果
        }
        for (int num : nums) {
            if (path.contains(num)) {
                continue;//如果路径里有num，跳出此次循环
            }
            path.add(num);
            combine(nums);
            path.remove(path.size()-1);
        }

    }

47. 全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

只做树层的去重，不做树枝的去重

• nums[i]=nums[i-1]并且used[i-1]=true说明nums[i-1]已经被加进了path中，这是数枝的重复

• nums[i]=nums[i-1]并且used[i-1]=false说明nums[i-1]已经被回溯成了false，这是树层的重复，要剪掉✂
  

• 新建了一个used数组来表示nums数组的使用情况

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;

    public List<List<Integer>> permuteUnique(int[] nums) {
        used = new boolean[nums.length];
        for (boolean b : used) {
            b=false;
        }
        Arrays.sort(nums);
        comine(nums,used);
        return res;
    }

    void comine(int[] nums, boolean[] used) {

        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));//收集结果
        }
        for (int i = 0; i < nums.length; i++) {
            if (i>0&&nums[i]==nums[i-1]&&used[i-1]==false) {
                continue;//当前数和前面的数相等并且前面的数还未使用时
            }
            if(used[i]==false){//当前元素还未使用时
                path.add(nums[i]);
                used[i]=true;//在path中添加元素，该位置标记为true
                comine(nums,used);
                path.remove(path.size() - 1);//回溯
                used[i]=false;//回溯
            }
        }
    }
}

---

下面是三道困难题，只是看了下题解，不是自己实现的

332. 重新安排行程

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

• 这次递归函数的返回值用的是boolean类型，因为满足条件的只有一种情况

class Solution {
    private LinkedList<String> res;
    private LinkedList<String> path = new LinkedList<>();

    public List<String> findItinerary(List<List<String>> tickets) {
        Collections.sort(tickets, new Comparator<List<String>>() {//tickets链表按字典序方式排序
            @Override
            public int compare(List<String> o1, List<String> o2) {
                return o1.get(1).compareTo(o2.get(1));
            }
        });
        path.add("JFK");//都要从JFK出发
        boolean[] used = new boolean[tickets.size()];//标记数组
        backTracking((ArrayList) tickets, used);
        return res;
    }

    public boolean backTracking(ArrayList<List<String>> tickets, boolean[] used) {
        if (path.size() == tickets.size() + 1) {
            res = new LinkedList(path);//航班数+1收集结果
            return true;
        }

        for (int i = 0; i < tickets.size(); i++) {
            // 如果当前的航班没有使用过 并且 当前航班的出发点等于目前飞行到的位置
            if (!used[i] && tickets.get(i).get(0).equals(path.getLast())) {
                // 路径中加入当前航班的终点
                path.add(tickets.get(i).get(1));
                // 标记当前航班使用过
                used[i] = true;

                // 往下递归
                if (backTracking(tickets, used)) {
                    return true;
                }

                // 如果当前路径往下递归并没有找到满足的条件就回溯
                used[i] = false;
                path.removeLast();
            }
        }
        return false;
    }
}

51. N 皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

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

    public List<List<String>> solveNQueens(int n) {
        char[][] chessboard = new char[n][n];//新建二维char数组
        for (char[] c : chessboard) {//遍历得到每一行
            Arrays.fill(c, '.');//每一行用 . 来填充
        }
        backTrack(n, 0, chessboard);
        return res;
    }


    public void backTrack(int n, int row, char[][] chessboard) {
        if (row == n) {
            res.add(Array2List(chessboard));//收集结果
            return;
        }

        for (int col = 0;col < n; ++col) {
            if (isValid (row, col, n, chessboard)) {
                chessboard[row][col] = 'Q';//如果当前位置校验成功的话，当前位置的char赋为Q
                backTrack(n, row+1, chessboard);//向下递归
                chessboard[row][col] = '.';//回溯（当前位置的Q重新赋为 . ）
            }
        }

    }


    //把二维char数组转换成list<String>链表
    public List Array2List(char[][] chessboard) {
        List<String> list = new ArrayList<>();//新建一个链表

        for (char[] c : chessboard) {
            list.add(String.copyValueOf(c));//每一行一维char数组转化成一个String，加入结果链表中
        }
        return list;
    }


    //校验方法
    public boolean isValid(int row, int col, int n, char[][] chessboard) {
        // 检查列
        for (int i=0; i<row; ++i) { // 相当于剪枝
            if (chessboard[i][col] == 'Q') {
                return false;
            }
        }

        // 检查45度对角线
        for (int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }

        // 检查135度对角线
        for (int i=row-1, j=col+1; i>=0 && j<=n-1; i--, j++) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
}

37. 解数独

编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。

• 挺难的这题，画树也可以画出来，但是太~~~复杂
  

class Solution {
    public void solveSudoku(char[][] board) {
        solveSudokuHelper(board);
    }

    private boolean solveSudokuHelper(char[][] board){
        //「一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，
        // 一行一列确定下来之后，递归遍历这个位置放9个数字的可能性！」
        for (int i = 0; i < 9; i++){ // 遍历行
            for (int j = 0; j < 9; j++){ // 遍历列
                if (board[i][j] != '.'){ // 跳过原始数字
                    continue;
                }
                for (char k = '1'; k <= '9'; k++){ // (i, j) 这个位置放k是否合适
                    if (isValidSudoku(i, j, k, board)){//校验成功
                        board[i][j] = k;//在棋盘中加入k
                        if (solveSudokuHelper(board)){ //向下递归
                            return true;// 如果找到合适一组立刻返回
                        }
                        board[i][j] = '.';//回溯
                    }
                }
                // 9个数都试完了，都不行，那么就返回false
                return false;
                // 因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！
                // 那么会直接返回， 「这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！」
            }
        }
        // 遍历完整个棋盘没有返回false，说明找到了合适棋盘位置了
        return true;
    }

    /**
     * 判断棋盘是否合法有如下三个维度:
     *     同行是否重复
     *     同列是否重复
     *     9宫格里是否重复
     */
    private boolean isValidSudoku(int row, int col, char val, char[][] board){
        // 同行是否重复
        for (int i = 0; i < 9; i++){
            if (board[row][i] == val){
                return false;
            }
        }
        // 同列是否重复
        for (int j = 0; j < 9; j++){
            if (board[j][col] == val){
                return false;
            }
        }
        // 9宫格里是否重复
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++){
            for (int j = startCol; j < startCol + 3; j++){
                if (board[i][j] == val){
                    return false;
                }
            }
        }
        return true;
    }
}

• 就只是看懂?

总结

• 所有的回溯问题都可以抽象成树?

• 回溯是递归的副产品，只要有递归就会有回溯

• for循环横向遍历，递归纵向遍历，回溯不断调整结果集

• 使用set去重的版本相对于used数组的版本效率都要低很多