力扣 216. 组合总和 III java实现

组合总和 III

这道题看了之后第一反应是使用 回溯+减枝，其实遇到这种类型的题，初看可能感觉无从下手，但是只要耐心画一下它的递归树就会很清晰：

由于题目要求list中不允许出现重复数字，所以我们需要传递一个下标，防止元素重复选取，代码如下:

class Solution {
    List<List<Integer>> list = new ArrayList<List<Integer>>();
    Deque<Integer> deque = new ArrayDeque<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        //排除边界条件
        if(n == 0 || k == 0 || n > 45 || k > 9){
            return list;
        }
        for(int i=1;i<=9;i++){
            deque.add(i);
            backTrack(i,k,n,new ArrayDeque<Integer>(deque));
            deque.pollLast();
        }
        return list;
    }
	//根据递归树回溯，求解
    public void backTrack(int index,int k,int n,Deque<Integer> deque2){
    	//减枝条件
        if(getSumOfDeque(deque2) > n){
            return;
        }
        if(deque2.size() == k){
            if(getSumOfDeque(deque2) == n){
                list.add(new ArrayList<Integer>(deque2));
            }else{
                return;
            }
        }
        index++;
        for(int j=index;j<=9;j++){
            deque2.add(j);
            backTrack(j,k,n,deque2);
            deque2.pollLast();
        }
    }
    //求deque列表元素和
    public int getSumOfDeque(Deque<Integer> deque) {
    	int sum = 0;
    	for(Integer i:deque) {
    		sum+=i;
    	}
    	return sum;
    }
}