216. Combination Sum III

Question

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

• Only numbers 1 through 9 are used.
• Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Solution

回溯，创建一个成员变量visited[]记录访问情况。

剪枝优化，遍历所有可选择的数字，将其加和，如果加和大于target则返回。
剪枝优化，每层级遍历的范围大于传入列表中的最后一个元素。
回溯，向下递归。

如果k等于0并且sum等于target则添加arr到列表ret中。

Code

class Solution {
    int[] visited;
    List<List<Integer>> ret;

    public List<List<Integer>> combinationSum3(int k, int n) {
        visited = new int[9];
        ret = new ArrayList<>();
        backTracking(k, n, new ArrayList<>(), 0);
        return ret;
    }
    
    private void backTracking(int k, int target, List<Integer> arr, int sum){
        if(k == 0 && sum == target) ret.add(new ArrayList<>(arr));
        int start = 1;
        if(arr.size() != 0) start =  arr.get(arr.size()-1)+1;
        for(int i = start ; i <= 9; i++){
            if(visited[i-1] == 1) continue;
            sum+=i;
            if(sum > target) return;
            visited[i-1] = 1;
            arr.add(i);
            
            backTracking(k-1, target, arr, sum);
            sum-=i;
            arr.remove(new Integer(i));
            visited[i-1] = 0;
        }
    }
}