day24 77

回溯算法 数字组合问题

77. 组合

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combine(int n, int k) {
        combinefun(n,k,1);
        return result;
    }

    public void combinefun(int n,int k,int startIndex){
        if(path.size()==k){
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i=startIndex;i<= n - (k - path.size()) + 1;i++){//也可以写成 n，但是这样会多做无用功，增大时间复杂度。
            path.add(i);
            combinefun(n,k,i+1);   
            path.removeLast();      //减枝
        }
    }
}

216. 组合总和 III

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    
    public List<List<Integer>> combinationSum3(int k, int n) {
        combinefun(n,k,1,0);
        return result;
    }
     public void combinefun(int n,int k,int startIndex,int sum){
        if(sum>n) return; //如果和大于n那就结束 往后继续没有意义 
        if(sum==n&&path.size()==k){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {
            path.add(i);
            sum+=i;
            combinefun(n,k,i+1,sum);
            path.removeLast();//减枝 
            sum-=i;   //回溯 是sum也要减回去
        }
    }
}