1.经典模版

private void backtrack("原始参数") {
    //终止条件(递归必须要有终止条件)
    if ("终止条件") {
    //一些逻辑操作（可有可无，视情况而定）
        return;
    }
    for (int i = "for循环开始的参数"; i < "for循环结束的参数"; i++) {
        //一些逻辑操作（可有可无，视情况而定）
        //做出选择
        //递归
        backtrack("新的参数");
        //一些逻辑操作（可有可无，视情况而定）
        //撤销选择
    }
}

2. 组合问题

1. 问题

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

2. 思路

递归遍历从1到n的数字，依次加入到list中去
如果满足终止条件则退出
3. 代码
```java public List> combinationSum3(int k, int n) { List> res = new ArrayList<>(); dfs(res, new ArrayList<>(), k, 1, n); return res; }

private void dfs(List> res, List list, int k, int start, int n) { //终止条件，如果满足这个条件，再往下找也没什么意义了 if (list.size() == k || n <= 0) { //如果找到一组合适的就把他加入到集合list中 if (list.size() == k && n == 0) res.add(new ArrayList<>(list)); return; } //通过循环，分别遍历9个子树 for (int i = start; i <= 9; i++) { //选择当前值 list.add(i); //递归 dfs(res, list, k, i + 1, n - i); //撤销选择 list.remove(list.size() - 1); } }

<a name="wwKHy"></a>
# leetcode 39.组合总数
<a name="O5OLp"></a>
## 1. 思路
通过回溯方法深搜，通过index记录当前起点位置，并且对该点进行深度搜索，然后保留住满足条件的路径<br />剪枝：当target<0时，后续的遍历节点肯定都不满足要求所以剪掉。
<a name="6fiPd"></a>
## 2. 代码
```java
public class CombinationSum {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates,int target){
        backtrack(new ArrayList<Integer>(),candidates,target,0);
        return res;
    }
    private void backtrack(ArrayList<Integer> integers, int[] candidates, int target, int index) {
        if(target<0){
            return;
        }
        if(target==0){
            ArrayList<Integer> arrayList = new ArrayList<>();
            arrayList.addAll(integers);
            res.add(arrayList);
            return;
        }
        for(int i=index;i<candidates.length;i++){
            int cur = target-candidates[i];
            integers.add(candidates[i]);
            backtrack(integers,candidates,cur,i);
            integers.remove(integers.size()-1);
        }
        return;
    }
}

leetcode 40.组合总数

每个数字在每个组合中只能使用一次,并且组合中不能出现重复样例

1. 思路

去掉重复集合思路

使用哈希表，需要自己写hashcode。
不重复就需要按顺序搜索，在搜索过程中检测分枝是否会出现重复结果。

先对数组升序排序，重复的元素一定不是排好序以后相同的连续数组区域的第 1个元素。也就是说，剪枝发生在：同一层数值相同的结点第 2、3 … 个结点，因为数值相同的第 1 个结点已经搜索出了包含了这个数值的全部结果，同一层的其它结点，候选数的个数更少，搜索出的结果一定不会比第 1 个结点更多，并且是第 1 个结点的子集。

2. 代码

public class CombinationSum2 {

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

  public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    Arrays.sort(candidates);
    Deque<Integer> deque = new ArrayDeque<>();
    dfs(candidates, target, deque, 0);
    return res;

  }

  private void dfs(int[] candidates, int target, Deque<Integer> deque, int index) {
    if (target == 0) {
      List<Integer> temp = new ArrayList<>();
      temp.addAll(deque);
      res.add(temp);
    }

    for (int i = index; i < candidates.length; i++) {
      if (target - candidates[i] == 0) {
        return;
      }
      if (i > index && candidates[i] == candidates[i - 1]) {
        continue;
      }

      deque.add(candidates[i]);
      dfs(candidates, target - candidates[i], deque, i + 1);
      deque.removeLast();
    }
    return;
  }
}

算法

回溯算法