首先给回溯算法模板，然后10道力扣经典回溯题，模板包教包会、力图统一化

最后的结论是：首先手绘回溯路径、然后分析选择列表、路径和结束条件、最后套模板yyds

回溯算法

[1] 参考了开源项目github.com/greyireland/algorithm-pattern
[2] 参考了labuladong的算法小抄必读文章中的回溯算法解题套路框架（不建议看）

1 定义及模板

背景

回溯法（backtrack）是 DFS 深度搜索一种，一般用于全排列，穷尽所有可能。遍历列表所有子集的过程实际是一个决策树的遍历过程。决策树的遍历过程为做选择和撤销选择的过程，这其中有着“一路选择到底，而后又一路撤销到起点”的过程，因此称为回溯。

回溯算法就是纯暴力穷举，复杂度一般都很高，时间复杂度一般 O(N!)。

回溯过程

通过分析发现，回朔法实现的三大关键点分别是：

一条路走到黑
回退一步
另寻他路

通过for 循环和递归来实现三个关键点，解释如下

for循环的作用在于另寻他路：你可以用for循环可以实现一个路径选择器的功能，该路径选择器可以逐个选择当前节点下的所有可能往下走下去的分支路径。例如：现在你走到了节点a，a就像个十字路口，你从上面来到达了a，可以继续向下走。若此时向下走的路有i条，那么你肯定要逐个的把这i条都试一遍才行。而for的作用就是可以让你逐个把所有向下的i个路径既不重复，也不缺失的都试一遍
递归可以实现一条路走到黑和回退一步：一条路走到黑：递归意味着继续向着for给出的路径向下走一步。如果我们把递归放在for循环内部，那么for每一次的循环，都在给出一个路径之后，进入递归，也就继续向下走了。直到递归出口（走无可走）为止。那么这就是一条路走到黑的实现方法。递归从递归出口出来之后，就会实现回退一步。
for循环和递归配合可以实现回朔：当递归从递归出口出来之后。上一层的for循环就会继续执行了。而for循环的继续执行就会给出当前节点下的下一条可行路径。而后递归调用，就顺着这条从未走过的路径又向下走一步。这就是回朔

代码模板

核心就是从选择列表里做一个选择，然后一直递归往下搜索答案，如果遇到路径不通，就返回来撤销这次选择。

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        //做选择
        将该选择从选择列表移除
        路径.add(选择)
        backtrack(路径, 选择列表)
        //撤销选择
        路径.remove(选择)
        将该选择再加入选择列表

路径：也就是已经做出的选择。cur
c结束条件：也就是到达决策树底层，无法再做选择的条件。

2 力扣经典回溯题型解答

78. 子集

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

套用模板

如果是直接套模板的话，就直接分析选择列表、路径和结束条件。

用原数组nums的索引index和表示选择列表，并用index索引表示做选择，每做一次选择后递归调用index+1，表示下一次要选择下一个索引的元素（因为要求子集）
用一个list集合List<Integer> cur储存本条选择路径、每条路径都是原数组的子集
结束条件？好像没有条件，任意路径都是子集，然后index索引的选择已经避免了重复

代码实现

class Solution {
    //定义结果集 和 选择路径
    List<List<Integer>> res;
    List<Integer> cur;
    public List<List<Integer>> subsets(int[] nums) {
        //初始化
        res = new ArrayList<List<Integer>>();
        cur = new ArrayList<Integer>();
        //回溯
        backtrack(nums,0);
        return res;
    }

    private void backtrack(int[] nums, int index){
        //结束条件 这里无
        res.add(new ArrayList<Integer>(cur));
        for(int i=index;i<nums.length;++i){
            //做选择 1添加到路径 2选择列表移除
            cur.add(nums[i]);
            i++;
            //递归调用 回溯
            backtrack(nums,i);
            //撤销选择 1移出路径 2选择列表加入
            cur.remove(cur.size()-1);
            i--;
        }
    }
}

遍历过程：自顶找一条路径到底，然后回溯撤回往前找。

46. 全排列

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

套用模板

如果是直接套模板的话，就直接分析选择列表、路径和结束条件。

每次对数组nums的for循环表示做选择，选择列表就是visited中未被访问的部分：即如果i索引已经被访问过了，就直接跳过本次循环、不做选择；否者选择nums[i]进入某条路径结果cur中
用一个数组visited = new boolean[nums.length]来表示已经访问过的路径。用一个List集合cur = new ArrayList<Integer>()来保存一条路径结果，每一条路径结果都是全排列的一种。
结束条件，当某条路径结果cur的长度等于原数组长度时，表示这条路径已经选择完毕，就将其加入到结果集中，并return结束。

代码实现

class Solution {
    //定义一个结果集res 和 一个存放路径选择cur的集合
    List<List<Integer>> res;
    List<Integer> cur;
    public List<List<Integer>> permute(int[] nums) {
        //初始化
        res = new ArrayList<List<Integer>>();
        cur = new ArrayList<Integer>();
        //定义记录历史路径的visited数组
        boolean[] visited = new boolean[nums.length];
        backtrack(nums,visited);
        return res;
    }
    private void backtrack(int[] nums, boolean[] visited){
        //是否满足结束条件
        if(cur.size()==nums.length){
            res.add(new ArrayList<Integer>(cur));
            return;
        }
        for(int i=0;i<nums.length;++i){
            if(visited[i]) continue;
            //如果在选择列表里面 1做选择 2选择列表移除
            cur.add(nums[i]);
            visited[i] = true;

            //递归调用、回溯
            backtrack(nums,visited);

            //撤销选择 1撤销选择 2选择列表加入
            cur.remove(cur.size()-1);
            visited[i]=false;
        }  
    }
}

遍历过程：自顶找一条路径到底，然后回溯撤回往前找。通过选择列表避免重复的元素选择。

90. 子集 II

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

套用模板

如果是直接套模板的话，就直接分析选择列表、路径和结束条件。

用原数组nums的索引index表示选择列表，并用index索引表示做选择，每做一次选择递归调用时index+1，表示选择下一个索引的元素。选择列表还要：
- 排除已经选择过了的值相等的元素nums[i]!=nums[i-1]，并用类似(i！=index)&&()的判断来区别是当前路径还是同一层的其他路径
- 去重的原则是当前树枝（本条路径）元素可以重复，而同一树层不能重复选择！
- i==index表示是当前路径….无论下一个是否重复都可以选！！
  - i!=index表示是通过for循环另寻出路，就是一条新的路径！！此时相同元素不能再次选择
路径用一个list集合cur保存某条选择的路径，
结束条件，因为已经去重，所以所有的路径都是子集，直接添加到结果集中。

~~这里有一个思考？什么时候用index索引来做选择，什么时候用visited数组来做选择呢？~~我终于知道了，所有的回溯都需要循环都需要索引index，区别只是从0开始循环还是从index开始循环。而仅仅只有类似全排列这样的题目才需要从0开始循环并用visited数组保存是否使用

代码实现

含重复元素的查找，因为要比较当前元素与上一个元素是否相等，都要先排序！！！

class Solution {
    List<List<Integer>> res;
    List<Integer> cur;
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        //初始化
        res = new ArrayList<List<Integer>>();
        cur = new ArrayList<Integer>();
        Arrays.sort(nums); //排序
        backtrack(nums,0);
        return res;
    }

    private void backtrack(int[] nums,int index){
        //是否满足结束条件、一律满足
        res.add(new ArrayList<Integer>(cur));
        
        for(int i=index;i<nums.length;++i){
            // nums[i]==nums[i-1]说明同一树层（其他路径）已经使用过这个值
            if(i!=index && nums[i]==nums[i-1]) continue;
            //做选择 1加入路径 2选择列表移除
            cur.add(nums[i]);
            i++;

            //递归调用，回溯
            backtrack(nums,i);

            //撤销选择 1移出路径 2选择列表加入
            cur.remove(cur.size()-1);
            i--;
        }
    }
}

47. 全排列 II

套用模板

我特么还是直接套模板考虑选择列表、路径和结束条件。

选择列表：每次对数组nums的for循环表示做选择，visited数组里面未访问的部分就是选择列表。
- 因为含重复元素，所以去重原则是同一树枝（同一条路径）允许重复、而同一树层不允许重复
- nums[i]==nums[i-1]&&visited[i-1]==false表示元素重复在同一树层上出现了，直接跳过
- 为了防止i-1越界，所以使用&&的特性来避免：i!=0&&nums[i]==nums[i-1]
路径：用一个list集合cur表示某一条路径，每一条完全的路径都是一个全排列；visited数组表示当前路径下已经访问过的位置
结束条件：当cur的长度等于原数组的长度，代表该路径完成，将该路径加到结果集中

代码实现

含重复元素的查找，因为要比较当前元素与上一个元素是否相等，都要先排序！！！

去重最关键的是：前一个元素没有选择的话，当前元素与之相同所以也不能选（前面的都不选、还轮不到你这个后面的）

class Solution {
    List<List<Integer>> res;
    List<Integer> cur;
    public List<List<Integer>> permuteUnique(int[] nums) {
        //初始化
        res = new ArrayList<List<Integer>>();
        cur = new ArrayList<Integer>();
        boolean[] visited = new boolean[nums.length];
        //回溯
        Arrays.sort(nums);
        backtrack(nums,visited);
        return res;
    }

    private void backtrack(int[] nums, boolean[] visited){
        //是否满足结束条件
        if(cur.size()==nums.length){
            res.add(new ArrayList<Integer>(cur));
            return;
        }
        for(int i=0; i<nums.length; ++i){
            //选择列表
            if(visited[i]) continue;
            if(i!=0&&nums[i]==nums[i-1]&&visited[i-1]==false) continue;
            //做选择， 1加入路径 2选择列表移除
            cur.add(nums[i]);
            visited[i]=true;
            //递归调用 回溯
            backtrack(nums,visited);
            //撤销选择，1移出路径 2选择列表加入
            cur.remove(cur.size()-1);
            visited[i]=false;
        }
    }
}

51. N 皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个不同的 n 皇后问题的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

皇后的走法是：可以横直斜走，格数不限。因此要求皇后彼此之间不能相互攻击，等价于要求任何两个皇后都不能在同一行、同一列以及同一条斜线上。

先决条件：这个问题本质上跟全排列问题差不多，决策树的每一层表示棋盘上的每一行；每个节点可以做出的选择是，在该行的任意一列放置一个皇后。

套用模板

直接看蒙，反正就是模板拿过来套，考虑选择列表、路径和结束条件（还是要背的）

选择列表，一个行的索引row表示每一行，每一次递归调用row++；for循环中对列col进行迭代；用一个char[][] cur来表示当前选择的路径；写一个函数判断当前row和col的位置是否可用，如下。
- 首先判断当前列直线上有没有使用过（遍历0到row行），如果有就return false
- 然后判断当前位置的左上斜直线的位置有没有使用过，如果有就return false
- 然后判断当前位置的右上斜直线的位置有没有使用过，如果有就return false
- 如果都没有就return true
路径，就是cur表示的二维数组集合，放了皇后的位置置字符Q，其他位置置字符.
结束条件，当row==n到了最后一行，表示各行都放置完成。将数组转换为list集合后加入结果集中

代码实现

注意点：1回溯调用每行row，内部循环调用每列col；2利用一个char数组来表示当前的选择（也就是当前的路径）；3写一个判断当前位置是否可用的函数；4写一个char数组转list集合的函数

class Solution {
    List<List<String>> res; //结果集
    char[][] cur; //某条路径
    public List<List<String>> solveNQueens(int n) {
        //初始化
        res = new ArrayList<List<String>>();
        cur = new char[n][n];
        for(int i=0;i<n;++i){
            for(int j=0;j<n;++j){
                cur[i][j]='.';
            }
        }
        //回溯函数
        backtrack(n,0);
        return res;
    }
    private void backtrack(int n, int row){
        //是否符合结束条件
        if(row==n){
            //将数组转为集合 再添加进结果集合种中
            res.add(arrayToList(cur));
            return;
        }

        for(int col=0;col<n;++col){
            //选择列表 写一个判断该位置是否可放的函数           
            if(!available(row,col)) continue; //如果不能放置就跳过
            //做选择
            cur[row][col] = 'Q';
            // 递归调用
            backtrack(n,row+1);
            //撤销选择
            cur[row][col] = '.';
        }
    }

    //将二维集合转为list集合
    private List<String> arrayToList(char[][] cur){
        List<String> list = new ArrayList<String>();
        for(int i=0;i<cur.length;++i){
            list.add(new String(cur[i]));//可以用cur[i]表示第i行的char数组!!
        }
        return list;
    }
    //判断当前位置是否可以放置皇后
    private boolean available(int row, int col){
        //判断 当前列上 有没有皇后
        for(int i=0;i<row;i++){
            if(cur[i][col]=='Q') return false;
        }
        //判断 当前位置的左上斜线上 有没有皇后
        for(int i=row-1,j=col-1; i>=0&&j>=0;i--,j--){
            if(cur[i][j]=='Q') return false;
        }
        //判断 当前位置的右上斜线上 有没有皇后
        for(int i=row-1,j=col+1;i>=0&&j<cur.length;i--,j++){
            if(cur[i][j]=='Q') return false;
        }
        return true;
    }
}

39. 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。

所有数字（包括 target）都是正整数。

解集不能包含重复的组合。

套用模板

直接看选择列表 、路径和结束条件：

选择列表有两个原则：1选择的那个元素不能使总和>target；2同一层的分枝不能使用前面分枝已经使用过的元素（避免最后求出两个相同的分枝）
- 对于总和，一个判断如果相加超过target跳过该次的遍历（target动态变化）
- 对于同一层上的元素不能重复使用前面分支的元素，直接用索引index就可以了，每次for遍历从从index开始。另外因为可以重复所以递归是不需要index+1；
路径用一个list集合cur存着，一条路走到黑、然后撤销再选择
结束条件，当target动态变化到0表示获得了一组解，此时加到结果集中

代码实现:

==从每一层的第 2 个结点开始，都不能再搜索产生同一层结点已经使用过的 candidate 里的元素。所以可以通过先排序然后用index的递归来实现！！！因为排序之后使用index，不会再次选择比我小的元素，就自然的剪枝了==

class Solution {
    List<List<Integer>> res;
    List<Integer> cur;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        //初始化
        res = new ArrayList<List<Integer>>();
        cur = new ArrayList<Integer>();
        //回溯函数
        Arrays.sort(candidates);
        backtrack(candidates,target,0);
        return res;
    }

    private void backtrack(int[] candidates, int target,int index){
        //是否满足结束条件
        if(target==0){
            res.add(new ArrayList<Integer>(cur));
            return;
        }
        for(int i = index;i<candidates.length;++i){
            //选择列表 如果小了后面的必然也小直接跳出
            if(target-candidates[i]<0) break;
            //做选择 1加入路径 2选择列表移出
            cur.add(candidates[i]);
            target -= candidates[i];
            //递归调用 回溯
            backtrack(candidates,target,i); //允许元素重复
            //撤销选择 1路径移出 2选择列表加入
            cur.remove(cur.size()-1);
            target += candidates[i];
        }
    }
}

40. 组合总和 II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

注意：解集不能包含重复的组合。

思路

排序后，同一层中，如果相同的数已经选择过了，这当前元素不应再选。
- if(i!=index&&candidates[i]==candidates[i-1]) continue;
排序之后如果target<0，直接break，因为后面的数都更大、一定不满足条件。直接剪枝后面所有的
因为同一个元素只能用一次，所以，回溯调用时使用 index+1

代码：

class Solution {
    List<List<Integer>> res;
    List<Integer> cur;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        res = new ArrayList<>();
        cur = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(candidates,target,0);
        return res;

    }

    private void backtrack(int[] candidates, int target, int index){
        if(target==0){
            res.add(new ArrayList<>(cur));
            return;
        }
        for(int i=index;i<candidates.length;i++){
            if(i!=index&&candidates[i]==candidates[i-1]) continue;
            if(target-candidates[i]<0) break;
            cur.add(candidates[i]);
            backtrack(candidates,target-candidates[i],i+1);
            cur.remove(cur.size()-1);
        }
    }
}

216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明： 1所有数字都是正整数。 2解集不能包含重复的组合。
示例 1: 输入: k = 3, n = 7 输出: [[1,2,4]]
示例 2: 输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]]

思路

k代表结果集的大小
n可以用来判断结束状态,选择集合就是1-9这9个数
当n或者k超过范围的时候直接可以判断结果集合为空

代码：

class Solution {
    List<List<Integer>> res;
    List<Integer> cur;
    public List<List<Integer>> combinationSum3(int k, int n) {
        //k代表结果集的大小
        //n可以用来判断结束状态,选择集合就是1-9这9个数
        //当n或者k超过范围的时候直接可以判断结果集合为空
        res = new ArrayList<>();
        if(n>45||k>9) return res;
        cur = new ArrayList<>();
        backtrack(k,n,1);
        return res;
    }

    private void backtrack(int k, int target,int index){
        if(cur.size()==k&&target==0){
            res.add(new ArrayList<>(cur));
            return;
        }
        if(cur.size()>=k||target<=0) return;
        for(int i=index;i<=9;i++){
            if(i>target) break;
            cur.add(i);
            backtrack(k,target-i,i+1);
            cur.remove(cur.size()-1);
        }
    }
}

17. 电话号码的字母组合

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

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。例如：
1
2
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

套用模板

分析选择列表、路径和结束条件

选择列表就是每个数字对应的三个字母。当前数字索引选择完之后，索引加一；每个数字索引下有3或4个字母选择，作为内部的for循环。
- 这里需要注意的是键盘最好用一个String数组储存，
路径用一个StringBuilder字符串来表示，注意删除元素的函数时是sb.deleteCharAt(sb.length()-1);
结束条件就是sb的长度达到给出数字字符的长度sb.length()==digits.length()

代码实现

class Solution {
    List<String> res;
    StringBuilder sb;
    //在这里定义一个字符串数组，根据索引找到字符串，然后再找字母
    String[] numMap = new String[]{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    public List<String> letterCombinations(String digits) {
        //初始化
        res = new ArrayList<String>();
        sb = new StringBuilder();
        //递归调用
        if(digits.length()<1) return res;
        backtrack(digits,0);
        return res;
    }
    
    private void backtrack(String digits,int index){
        //是否满足结束条件
        if(sb.length()==digits.length()){
            res.add(sb.toString());
            return;
        }
        char c = digits.charAt(index);
        String numString = numMap[c-'0'];
        for(int i=0;i<numString.length();++i){
            //选择列表就是numString
            //做选择
            sb.append(numString.charAt(i));
            //回溯
            backtrack(digits,index+1);
            //撤销选择
            sb.deleteCharAt(sb.length()-1);
        }
    }
}

131. 分割回文串

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

回文串 是正着读和反着读都一样的字符串。

套用模板

不理解题目直接套模板的方法是错的，还是要先分析如何遍历、如何剪枝、选择列表是哪些，也就是要先用一个简单的例子画出如上的递归树模型，一般是一个多叉树。然后看看递归的过程：

根据索引截取字串，而每一条路径选择子串元素的原则就是判断这个子串元素是不是回文性质的。截取子串是需要前后两个索引，start和end，start就是回溯函数的参数index，end为for循环遍历的i，直到字符串末尾。

然后进行分析选择列表、路径和结束条件

选择列表简单来讲就是所有可能的子字符串。选择这样的遍历方式
- 起始索引start由递归函数的索引index调用递增（外层）
- 结束索引end由函数内部的for循环遍历（内层），由start到字符串结尾
- 根据索引得到子字符串之后，如果该子串不是回文串就直接跳过``
路径由List<String>集合cur表示，选择和撤销操作
结束条件指找到了一整个集合，里面包含的所有字符串组合起来就是原字符串。这意味着内层for循环需要找到最后一位字符，
- 如果我们已经搜索完了字符串的最后一个字符，那么就找到了一种满足要求的分割方法。这里需要index=n 因为start=end+1，所以如果end=len-1，那么start=len就结束了

代码实现

class Solution {
    //定义结果集和路径
    List<List<String>> res;
    List<String> cur;
    public List<List<String>> partition(String s) {
        //初始化
        res = new ArrayList<List<String>>();
        cur = new ArrayList<String>();
        //回溯函数
        backtrack(s,0);
        return res;
    }
    
    private void backtrack(String s,int start){
        //结束条件 处理到最后一个字符
        if(start==s.length()){
            res.add(new ArrayList<String>(cur));
            return;
        }
        for(int end=start;end<s.length();end++){
            //选择列表 如果子串不是回文 则直接跳过（剪枝）
            if(!isPartition(s,start,end)) continue;
            //做选择 1加入路径 选择列表移出
            cur.add(s.substring(start,end+1));//实际上是取[start,end]这部分的子串
            //start = end+1; //下一个要从end+1索引开始找了
            //回溯
            backtrack(s,end+1);
            //撤销选择 1路径移出 2选择列表加入
            cur.remove(cur.size()-1);
            //start = 原本的start;
        }
    }

    //判断是否是回文子串
    private boolean isPartition(String s, int start, int end){
        //判断s字符串[start end]范围的子字符串是否回文
        while(start<end){
            if(s.charAt(start)!=s.charAt(end)) return false;
            start++;
            end--;
        }
        return true;
    }

}

此处判断是否为回文串的函数还可以优化，使用动态规划利用之前的判断结果，减少下循环的次数，本处不着重故不表。

93. 复原 IP 地址

1 官方题解

思路其实就是遍历+筛选，“对所有可能的字符串分隔方式进行搜索，并筛选出满足要求的作为答案。”

使用一个List集合res表示结果集合。
使用一个int[]数组numCur表示路径，长度为4，储存每一次路径的结果。添加进结果集时需要转换为一个字符串。(用list集合也可以，更统一吧)
使用一个int变量times表示当前搜索IP地址的第几段times∈{0,1,2,3}。
使用一个索引start表示搜索的开始位置，由于 IP 地址的每一段必须是 [0,255] 中的整数，因此我们从start 开始，从小到大依次枚举当前这一段 IP 地址的结束位置end，如果满足范围要求就加入到路径中。

考虑结束条件、选择列表和路径

结束条件，start索引或者times任意一个达到最大都应该结束
- 如果两个同时达到最大，就将当前路径添加进结果集，并返回
- 如果只有一个先达到最大，就直接返回、继续寻找下一个可能的路径
选择列表，什么时候跳过选择
- 首先考虑一种特殊情况，当是0元素开头时，直接将其设为一段添加进结果集，递归迭代找一个个路径
- 一般情况就先判断start和end之间的当前值，是否在0-225之间，在、就添加递归撤销
路径，为方便比较大小，此处路径就由一个长为4的int数组表示，每个索引代表IP的一段值

代码实现

class Solution {
    List<String> res;
    List<Integer> cur;
    public List<String> restoreIpAddresses(String s) {
        //一些细节的地方还是蛮麻烦的..
        //官方题解的思路 其实就是没有刻意的去剪枝。。只是简单的判断了一下每次选择元素的范围
        //自己写一遍吧 递归函数中包含start、times,分别表示开始索引和ip地址的第几位
        res = new ArrayList<>();
        cur = new ArrayList<>();
        backtrack(s,0,0);
        return res;
    }

    private void backtrack(String s, int start, int times){
        if(start==s.length()&&times==4){
            StringBuilder sb = new StringBuilder();
            for(int i=0;i<cur.size();i++){
                sb.append(cur.get(i));
                if(i!=3) sb.append(".");
            }
            res.add(sb.toString());
            return;
        }
        //有一个遍历完了 另一个没完就直接返回（该路径不满足要求）
        if(start==s.length() || times==4) return; 
        //先特判一下0
        if(s.charAt(start)=='0'){
            cur.add(0);
            backtrack(s,start+1,times+1);
            cur.remove(cur.size()-1);
        }

        for(int end = start;end<s.length();end++){
            int num = Integer.parseInt(s.substring(start,end+1));
            if(num>255||num==0) break;
            cur.add(num);
            backtrack(s,end+1,times+1);
            cur.remove(cur.size()-1);
        }
    }
}

2 我的思路

其实我的思路也没有错吧，，，判断位数和的大小是否满足条件不满足直接退出，，，试一试

选择列表，当前段的位数应该满足max(1,afterLength-3*(3-times)<=end-start+1<=3
- 并且当位数为3时应该<=255，，如果值大于255,直接break
- 如果位数小于max（1，…），就continue，增加位数
- 也需要单独考虑0为首位的情况
路径，用一个list来保存。正确的路径先转为String然后再加入结果集中。
结束条件，与官方题解一致

代码实现

class Solution {
    //定义结果集和路径
    List<String> res;
    List<Integer> cur;
    public List<String> restoreIpAddresses(String s) {
        //初始化
        res = new ArrayList<String>();
        cur = new ArrayList<Integer>();
        //回溯函数
        backtrack(s,0,0,s.length());
        return res;
    }
    private void backtrack(String s, int start, int times, int afterLength){
        //结束条件 1同时达到最大 有结果 2只有一个达到最大 没结果
        if(start==s.length() && times==4){
            //将路径转换为字符串 加入到结果集中
            StringBuilder sb = new StringBuilder();
            for(int i=0;i<cur.size();++i){
                sb.append(cur.get(i));
                if(i!=3) sb.append('.');
            }
            res.add(sb.toString());
        }
        if(start==s.length() || times==4) return;

        //考虑0出现的特殊情况
        if(s.charAt(start)=='0'){
            if(1<Math.max(1,afterLength-3*(3-times))){
                return;
            }else{
                cur.add(0);
                backtrack(s,start+1,times+1,afterLength-1);
                cur.remove(cur.size()-1);
            }
        }

        //一般情况
        for(int end=start;end<s.length();++end){
            //这里只考虑位数
            int old = Integer.parseInt(s.substring(start,end+1));
            if(end-start+1>3 || old>255 ||old==0) break;
            if(end-start+1<Math.max(1,afterLength-3*(3-times))) continue;
            //做选择
            cur.add(old);
            //递归
            backtrack(s,end+1,times+1,s.length()-end-1);
            //撤销选择
            cur.remove(cur.size()-1);
        }
    }
}

剑指 Offer 38. 字符串的排列

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

1 解法一使用hashset去重 44ms

与含有重复元素的数字的全排列问题相同，但开始不了解字符串的排序，所以第一的想法就是直接生成所有可能的排列情况（一个元素只能使用一次），然后将每种可能也就是路径添加进set集合中实现去重，也就获得了最终的结果集合。未避免元素重复使用、这里因为是全排列问题（元素的使用没有先后关系、只有使用与否的判断），所以需要定义一个visitied数组，表示访问的历史路径。

选择列表，未选择的任意一元素。内层循环从0开始知道最大长度，如果已经访问过就跳过if(visited[i]) continue;
结束条件，路径sbCur的长度等于原字符串的长度
路径，用一个StringBuilder表示、append()添加 delectCharAt()移除

代码实现

class Solution {
    //这题还有些特殊 字符串不能排序，不能用判断的方法剪枝同层相同的元素
    //用hashSet去重 作为结果集的集合 那么选择列表就变为了下一个索引元素 无需判断
    //路径 可以用一个list集合来存（虽然优点浪费） 或者用StringBuilder也可以

    //定义结果集和路径
    Set<String> hashset;
    StringBuilder sbCur;
    public String[] permutation(String s) {
        //初始化
        hashset = new HashSet<String>();
        sbCur = new StringBuilder();
        //回溯函数
        boolean[] visited = new boolean[s.length()];
        backtrack(s,visited);
        return hashset.toArray(new String[0]);

    }
    private void backtrack(String s, boolean[] visited){
        //结束条件 当sbCur的长度等于s.length()
        if(sbCur.length()==s.length()){
            hashset.add(sbCur.toString());
            return;
        }
        for(int i=0;i<s.length();++i){
            //选择列表 已经用的元素不能再次使用
            if(visited[i]) continue;
            //做选择
            sbCur.append(s.charAt(i));
            visited[i]=true;
            //递归调用
            backtrack(s,visited);
            //撤销选择
            sbCur.deleteCharAt(sbCur.length()-1);
            visited[i]=false;
        }
    }
}

2 解法二字符串排序手动去重 10ms

参考含重复数字的全排列问题，同样对字符串的字符先排序，然后遍历排序。

选择列表，同一树层，不能选择已经使用过的元素内层循环i从0到最大长度
- char[i]==char[i-1]&&visited[i-1]==false 表示如果元素相同、前一个元素没有用、你也就必然用不了，直接跳过
结束条件，同样是路径长度等于原字符串长度
路径，用StringBuilder存结果，用visited数组当前选择的历史路径

代码实现：没什么意思，跟含重复元素的全排列是一样的…

class Solution {
    //定义结果集和路径
    List<String> res;
    StringBuilder sbCur;
    public String[] permutation(String s) {
        //初始化
        res = new ArrayList<String>();
        sbCur = new StringBuilder();
        boolean[] visited = new boolean[s.length()];
        char[] ch = s.toCharArray();
        Arrays.sort(ch); //应该就是这么排序吧
        //回溯函数
        backtrack(ch,visited);
        return res.toArray(new String[0]);
    }
    private void backtrack(char[] ch,boolean[] visited){
        if(sbCur.length()==ch.length){
            res.add(sbCur.toString());
            return;
        }
        for(int i=0;i<ch.length;++i){
            //选择列表
            if(visited[i]) continue;
            if(i!=0&&ch[i]==ch[i-1]&&visited[i-1]==false) continue;
            //做选择 1添加路径 2选择列表移除
            sbCur.append(ch[i]);
            visited[i] = true;
            //递归调用
            backtrack(ch,visited);
            //撤销选择 1路径移出 2选择列表加入
            sbCur.deleteCharAt(sbCur.length()-1);
            visited[i] = false;
        }
    }
}

491. 递增子序列

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中至少有两个元素。你可以按任意顺序返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例 1：输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例 2：输入：nums = [4,4,3,2,1]
输出：[[4,4]]

思路一：通过剪枝和set集合去重的方式

决策树的图是很好画的，就是暴力选择，选择当前元素i后，下一层的选择就是i之后的所有元素
涉及到两个剪枝的操作：1下一层元素不能小于上层元素 2 同一层选择相同元素的需要剪枝
- 1的操作是必须的，因为要求“递增子序列”。每次比较判断一下就好了，不满足就跳过
- 2 的操作，一半在数组已经排序时，我们可以通过判断与建一个元素相等来剪枝。但是这里求子序列，数组是不可以排序的，所以先想到用set做结果集去重！！

代码：

class Solution {
    Set<List<Integer>> set;
    List<Integer> cur;
    public List<List<Integer>> findSubsequences(int[] nums) {
        //决策树比较好画，就是去重的话因为不能排序，所以只能用set去重
        //（同一层已经使用过的元素，只要值相等都不能再用）
        set = new HashSet<>();
        cur = new ArrayList<>();
        backtrack(nums,0);
        return new ArrayList<>(set);
    }

    private void backtrack(int[] nums, int index){
        if(cur.size()>=2){
            set.add(new ArrayList<>(cur));
            //return; //这里千万不能return
        }
        for(int i=index;i<nums.length;i++){
            if(i!=index&&nums[i]==nums[i-1]) continue;
            if(cur.size()>=1 && nums[i]<cur.get(cur.size()-1)) continue;
            cur.add(nums[i]);
            //System.out.println("回溯前"+cur);
            backtrack(nums,i+1);
            //System.out.println("回溯后"+cur);
            cur.remove(cur.size()-1);
        }
    }
}

思路二：用一个set数组记录本层使用过的元素，手动剪枝去重，结果集中list集合

这个思路是完全正确的，唯一要考虑的是，如何保存本层已经选择过的所有元素。
- 回溯中的backtrack()调用实际上是向下层继续选择。而for循环是只选择其他的路径！！所以一个for循环对应着一层中的所有路径！！在for循环上new 一个Set集合。迭代时将nums[i]加入集合中。没进入一层会重新new一个set，所以无需考虑回溯删除set中的元素。
- 也开始通过一个桶数组boolean[201]，来存是否当前值的元素被使用过
剪枝条件就是同层元素不能选择前面用过的值相等的元素if(i!=index&&set.contains(nums[i])) continue;

代码

class Solution {
    List<List<Integer>> res;
    List<Integer> cur;
    
    public List<List<Integer>> findSubsequences(int[] nums) {
        //决策树比较好画，就是去重的话用set存已经使用过的值
        res = new ArrayList<>();
        cur = new ArrayList<>();
        backtrack(nums,0);
        return res;
    }
    private void backtrack(int[] nums, int index){
        if(cur.size()>=2){
            res.add(new ArrayList<>(cur));
            //return; //千万不能+return
        }
        Set<Integer> set  = new HashSet<>();
        for(int i=index;i<nums.length;i++){
            if(i!=index&&set.contains(nums[i])) continue;
            if(cur.size()>=1 && nums[i]<cur.get(cur.size()-1)) continue;
            set.add(nums[i]); //set集合存本层已经使用过的元素，无需回溯！！
            cur.add(nums[i]);
            backtrack(nums,i+1);
            cur.remove(cur.size()-1);
        }
    }
}

3、总结

什么时候要用到回溯的算法？

当题目种出现排列、所有可能的排序方案，这样需要全局遍历的时候

模板中最关键的其实是选择列表。

不重复元素子集问题的选择列表，是下一个索引的位置；
重复元素子集问题的选择列表，是同一个树层不能有值相同的元素，即排序之后的数组，当当前索引与前一个相等并且前一个元素没有被访问时，就不能选择当前元素（轮不到你，前一个相等的都没选，为什么要选你这个后面的呢？）if(i!=index&&nums[i]==nums[i-1]) continue;
不重复元素的全排列问题的选择列表，是当前索引处未被访问；if(visited[i]) continue;
重复元素的全排列问题的选择列表，两个
- 当前元素已经使用过，就不能选if(visited[i]) continue;
- 是同一树层不能有值相同的元素（轮不到你） if(i!=0&&nums[i]==nums[i-1]&&visited[i-1]==false) continue;
N皇后问题的选择列表就是当前行row的某几个列col；遍历这行的每一列，不能放置的地方就跳过if(!available(row,col)) continue;

这里又要思考一个问题了，什么时候回溯函数中要带index索引，什么时候不要？

全排列、全排列2中没有用到index迭代；子集和子集2以及N皇后问题中用到了index索引，其共同点在于某一行（或某个元素）选择之后就不再需要、已经不在选择队列之中了，并且每选择完某一行（或某个元素）后需要继续向下一行（下一个元素）继续做同样的选择。这个时候就需要索引index+1。（先暂且这么猜这么用）

再修改一下，只有像全排列这种，选择了一个数对选择下一个数没有先后关系（只有是否重复的关系）时，就不用索引index遍历，其他大多数时刻都需要索引：

一种情况是有两层循环，像N皇后这种走棋牌格
一种情况是有明显的前后关系，
- 如子集问题选完这一个、需要判断下一个。
- 如求组合总数，判断完当前元素需要继续判断当前元素（因为可以重复）。
- 如分隔回文串、复原IP地址，下一个分隔的开始位置，是由前一个分隔的结束位置判断的

还有一个问题，什么时候回溯函数中要带visited[]数组，什么时候不要？

现在想来就是只有全排列这种遍历需要从0开始的就需要借助visited数组判断是否使用过，其他用index索引的情况都不需要！！

反正就是套模板呗，模板永远滴神！！

4 补充题

15. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2：

输入：nums = []
输出：[]

这题使用回溯会超时，但也不失为一种解决思路

思路：

先对数组排序、避免同层选到相同值得数，另外遍历时索引index不断+1，作为选择列表，即选择下一个索引位置的元素
路径，即以作得选择由一个cur得list集合保存
结束条件，cur长度为3，且其元素值之和为0。结果集先用set保存以便去重

代码：

class Solution {
    //典型的回溯算法
    Set<List<Integer>> set;
    List<Integer> cur;
    public List<List<Integer>> threeSum(int[] nums) {
        cur = new ArrayList<>();
        set = new HashSet<>();
        //调用回溯函数 
        Arrays.sort(nums);
        backtrack(nums,0);
        return  new ArrayList<>(set);
    }
    private void backtrack(int[] nums, int index){
        //结束条件 cur的size为3且3数之和为0
        if(cur.size()==3 && cur.get(0)+cur.get(1)+cur.get(2)==0){
            set.add(new ArrayList<Integer>(cur));
            return;
        }
        //遍历集合 选择列表
        for(int i=index;i<nums.length;i++){
            //做选择
            cur.add(nums[i]);
            //回溯调用
            backtrack(nums,i+1);
            //撤销选择
            cur.remove(cur.size()-1);
        }
    }
}

落风的风

回溯算法模板-力扣题解

回溯算法

1 定义及模板

背景

回溯过程

代码模板

2 力扣经典回溯题型解答

78. 子集

46. 全排列

90. 子集 II

47. 全排列 II

51. N 皇后

39. 组合总和

40. 组合总和 II

216. 组合总和 III

17. 电话号码的字母组合

131. 分割回文串

93. 复原 IP 地址

剑指 Offer 38. 字符串的排列

491. 递增子序列

3、总结

4 补充题

15. 三数之和