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