组合（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);}}
}
