216. Combination Sum III

Find all possible combinations ofknumbers that add up to a numbern, 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]]

Analysis:

DFS, each recursion loop through curPosition to 9, next recursion should always start at postion = i + 1 so that there is no duplicate being used from 1 - 9.

Complexity:

Time: O(C 9 k) - combination of picking k elements from 1-9

Space: O(K)

Code:

public class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> returnList = new ArrayList<List<Integer>>();

        if(k == 0 || k > 9 || (1+k)*k/2 > n || (9-k+1 + 9)*k/2 < n){
            return returnList;
        }

        dfs(n, 1, k, returnList, new ArrayList<Integer>());
        return returnList;
    }

    public void dfs(int target, int pos, int k, List<List<Integer>> returnList, List<Integer> tempList){
        if(tempList.size() == k){
            if(target == 0){
                returnList.add(new ArrayList<Integer>(tempList));
            }
            return;
        }

        for(int i = pos; i <= 9; i++){
            if(target >= i){
                tempList.add(i);
                dfs(target-i, i+1, k, returnList, tempList);
                tempList.remove(tempList.size() - 1);
            }
        }
    }
}