216. Combination Sum III

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

[[1,2,6], [1,3,5], [2,3,4]]

backtracking

public class Solution {

    List<List<Integer> > res = new ArrayList<>();
    public List<List<Integer>> combinationSum3(int k, int n) {
        sum3(1, 0, n, 0, k, new ArrayList<Integer>());
        return res;
    }


    private void sum3(int val, int curSum, int n, int count, int k, List<Integer> list){
        if(count > k || curSum > n) return;

        if(count == k && curSum == n){
            List<Integer> l = new ArrayList<>(list);
            res.add(l);
            return;
        }

        for(int i=val; i<10 ; i++){
            list.add(i);
            sum3(i+1, curSum+i, n, count+1, k, list);
            list.remove(list.size()-1);

        }

    }
}

better form

public class Solution {
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        if(k > n) return res;

        sum3(1, 9, 0, n, 0, k, new ArrayList<Integer>());
        return res;

    }

    void sum3(int start, int stop, int cur, int target, int count, int k, List<Integer> list){
        if(count > k) return;
        if(count == k){
            if(cur == target){
                res.add(new ArrayList<Integer>(list));
            }
            return;
        }

        for(int i=start; i<=stop; i++){
            if(cur + i > target) break;
            list.add(i);
            sum3(i+1, stop, cur+i, target, count+1, k, list);
            list.remove(list.size()-1);
        }
    }
}