回溯法理论基础
回溯法是一种搜索算法，从本质上来说，回溯法是一种穷举法，穷尽其所有可能而举其可行解；尽管回溯法有剪枝等操作，但也只是去除一些明显不可行的部分，仍改变不了回溯法暴力搜索的本质。
虽然回溯法是一种暴力求解算法，但很多时候我们也只能选择这种算法。
回溯法是以深度优先的方式系统地搜索问题的解，它适用于解一些组合数较大的问题。
回溯法可以解决的问题
组合问题：从n个数的集合中选出k个数的组合问题排列问题：对n个数进行排列有多少种排列方法子集问题：一个集合种有多少符合条件的子集问题棋盘问题：典型的有n皇后问题、解数独问题回溯法解题模板
void backtrack(参数) {if (终止条件) {收集结果;return;}for (选择：本层集合中元素（集合大小为本层节点的数量）) {处理节点;backtrack(路径，选择列表，其他参数); // 递归回溯，撤销处理操作;}}
回溯法之组合问题
组合问题基础
力扣第39题39. 组合总和 - 力扣（LeetCode） (leetcode-)
求一个数组中使数字和为目标值的所有组合，属于典型的组合问题，接下来套用模板进行解决。
首先我们需要一个总的链表来存放已经找到的组合，还需要一个存放当前组合的链表
List<List<Integer>> res=new ArrayList<>(); //存放可行解的链表List<Integer> l=new ArrayList<>(); //存放当前结果的链表
接下来定义我们的回溯函数backtrack(),这也是回溯法的重中之重，由于回溯法的参数一般比较复杂，我们可以先不填写参数，需要用到的时候再加入参数。
为了判断当前组合是否满足条件，我们需要设置一个整型变量sum，用于记录当前组合的数字和，回溯终止条件是sum==target即当前数字之和等于给定的目标值，并将其加入到结果集中；
if(sum==target){ //收集结果res.add(new ArrayList<Integer>(l));return;}
如果sum值小于目标值，继续进行深度搜索；在本层集合中依次选择元素都尝试将其加入当前组合中，在for循环中先将其加入组合中，并修改sum值，然后回溯递归进行下一层操作，回溯完成后，不要忘了撤销刚才的操作。
for(int i=startindex;i<candidates.length;i++){sum+=candidates[i];l.add(candidates[i]);backtrack(res,candidates,target,l,sum,i);l.remove(l.size()-1); //回溯sum=sum-candidates[i];}
我们还可以加入剪枝操作，当sum值已经大于目标值target时，就不需要进行接下来的操作了，直接break。加入剪枝操作之后的代码为：
for(int i=startindex;i<candidates.length;i++){int tmp=sum+candidates[i];if(tmp<=target){sum+=candidates[i];l.add(candidates[i]);backtrack(res,candidates,target,l,sum,i);l.remove(l.size()-1);//回溯sum=sum-candidates[i];}else break;//剪枝操作}
在主函数中我们需要对数组进行排序，可以减少重复的回溯组合，然后调用回溯函数进行求解。
总的代码如下:
class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> res=new ArrayList<>();List<Integer> l=new ArrayList<>();Arrays.sort(candidates);backtrack(res,candidates,target,l,0,0);return res;}public void backtrack(List<List<Integer>> res,int[] candidates,int target,List<Integer> l,int sum,int startindex){if(sum==target){ //收集结果res.add(new ArrayList<Integer>(l));return;}for(int i=startindex;i<candidates.length;i++){int tmp=sum+candidates[i];if(tmp<=target){sum+=candidates[i];l.add(candidates[i]);backtrack(res,candidates,target,l,sum,i);l.remove(l.size()-1); //回溯sum=sum-candidates[i];}else break;}}}
组合问题（去重）
力扣第40题40. 组合总和 II - 力扣（LeetCode） (leetcode-)
此题和上题的描述大致相同，但有两个区别，这也导致了此题的答案与上题有两处不同
数组中的每个数字只能使用一次解集不能包含重复的组合
这是两个不同的限制要求
对于第一个要求，每个数字只能使用一次，我们考虑上题的backtrack函数中的startIndex参数，由于上题中没有要求每个数字只能使用一次，我们传给下一层的startIndex参数是i,这代表下一层还可以继续使用自己，所以在此题中，i这一个数字在下层肯定不能继续使用，于是传给下一层的参数是i+1
backtrack(res, list, candidates, sum, target, i+1);
对于第二个要求，是结果不能包含重复的组合，其实重复的组合是由于数组中有重复的元素造成的，比如此题中有两个1，第一个1和数字7组成一个组合得到target数字8，第二个1同样可以和7组成一个组合也可以得到target数字8，这两个组合都是可行解，且每个数字只使用一次，但是却是重复的组合。
我们在回溯开始之前已经对数组进行了排序，在for循环中遇到第二个1、第三个1或是更多的1时可以直接跳过此循环，因为此时产生的组合都已经加入到结果集中了（第一个1产生的）。
if(i>startIndex && candidates[i]==candidates[i-1]) continue;
完整的代码如下：
public List<List<Integer>> combinationSum2(int[] candidates, int target) {List<List<Integer>> res=new ArrayList<>();List<Integer> list=new ArrayList<>();Arrays.sort(candidates);backtrack(res,list,candidates,0,target,0);return res;}void backtrack(List<List<Integer>> res,List<Integer> list,int[] candidates,int sum,int target,int startIndex){if(sum==target){res.add(new ArrayList<Integer>(list));return;}for(int i=startIndex;i<candidates.length;i++){if(i>startIndex && candidates[i]==candidates[i-1]) continue ; //去重int temp=sum+candidates[i];if(temp<=target){list.add(candidates[i]);sum+=candidates[i];backtrack(res, list, candidates, sum, target, i+1); //数组中每个数字只使用一次sum-=candidates[i];list.remove(list.size()-1);}else break;}}
组合问题练习
力扣第77题77. 组合 - 力扣（LeetCode） (leetcode-)
做完上面两个题之后相信对于回溯法做组合问题已经有了大致思路，不妨做一下此题，和上述题目异曲同工。
public List<List<Integer>> combine(int n, int k) {List<List<Integer>> res=new ArrayList<>();List<Integer> list=new ArrayList<>();backtrack1(res,list,n,k,0,1);return res;}void backtrack1(List<List<Integer>> res,List<Integer> list,int n,int k,int count,int startIndex){if(count==k){res.add(new ArrayList<>(list));return;}for(int i=startIndex;i<n+1;i++){list.add(i);count++;backtrack1(res,list,n,k,count,i+1);count--;list.remove(list.size()-1);}}
