代码随想录（回溯）

组合（Leetcode77）

思路 用递归每次遍历从1-n得数，然后list来记录是不是组合到k个了，然后这个每次for循环的开始不能和上一个值的开始重复，所以设置个遍历开始索引startindex  
class Solution {static List<List<Integer>> result;static List<Integer> list;static int q;public  static List<List<Integer>> combine(int n, int k) {result = new ArrayList<>();list = new ArrayList<>();q = k;dfs(n,k,1);return  result;}public static void dfs(int n,int k,int startIndex){if(list.size()==k){result.add(new ArrayList<>(list));return;}for (int i = startIndex;i<=n - (k - list.size()) + 1;i++){  //优化list.add(i);dfs(n,k,i+1);list.remove(list.size()-1);}}
}

组合总和（Leetcode216）

1、为每个位置遍历一个数（用startIndex来防止重复）2、用sum来记录当前的总和 如果已经超过了则return 如果存入的数已经达到k个就判断sum是否等于n然后返回
class Solution {static List<List<Integer>> result;static List<Integer> list;public List<List<Integer>> combinationSum3(int k, int n) {result = new ArrayList<>();list = new ArrayList<>();dfs(n,k,1,0);return result;}public static void dfs(int n,int k,int startIndex,int sum){if(sum>n){//当前组合已经大于sum 不可能再等于n了 直接returnreturn;}if(list.size()==k){if (sum==n){  //判断是否sum==nresult.add(new ArrayList<>(list));}return;}for(int i = startIndex;i<=9-(k-list.size())+1;i++){  从start开始防止重复list.add(i);dfs(n,k,i+1,sum+i);  //每次记录总和   list.remove(list.size()-1);}}
}