Leetcode 216. Combination Sum III

Description:

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]]

Thinking:

The only difference is the return condition of the helper function.

Complexity:

The time complexity is n!.

Step:

1. Check whether input is valid
2. create helper function.

Code:

public class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        if(k > n) return new ArrayList<List<Integer>>();
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        combinationSumHelper(result,list,n, k, 1);
        return result;
    }
     private void combinationSumHelper(List<List<Integer>> result, List<Integer> list, int sum, int k, int pos){
        if(list.size() == k && sum == 0){
            result.add(new ArrayList<Integer>(list));
            return;
        }

        for(int i = pos; i <= 9; i++){
            list.add(i);
            combinationSumHelper(result,list,sum-i, k, i+1);
            list.remove(list.size()-1);
        }
    }
}

Conclusion:

Nothing special.