King Of Interviews

Combination Sum III: 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.

Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.

Example 2:

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.

Example 3:

Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Using 4 different numbers in the range [1,9],
the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1,
there are no valid combination.

Constraints:

2 <= k <= 9
1 <= n <= 60

Try this Problem on your own or check similar problems:

Solution:

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<>();
        helper(k, n, 0, 1, new ArrayList<>(), result);
        return result;
    }
    private void helper(int k, int n, int currentSum, int start, List<Integer> currentList, List<List<Integer>> result){
        if(currentList.size() > k) return;
        if(currentSum == n && currentList.size() == k){
            result.add(new ArrayList<>(currentList));
            return;
        }
        for(int i = start; i <= 9; ++i){
            if(n >= currentSum + i){
                currentList.add(i);
                helper(k, n, currentSum + i, i + 1, currentList, result);
                currentList.remove(currentList.size() - 1);
            }
        }
    }
}

Time/Space Complexity:

Time Complexity: O(k*9^k)
Space Complexity: O(k)

Explanation:

Almost identical to Combination Sum with a twist that we can’t reuse numbers, and we can only choose from 1..9 range and we have to have the combination of size k. Those restrictions simplify the problem. We have the same helper function with the following changes to match the problem statement:

we return if the currentList size is larger than k since the combination size must match k
we only loop over 1..9 range and we only choose number that doesn’t add up to number larger than n when added to the currentSum
We have start which is ever increasing when passed to next recursive calls (we can’t reuse elements)

Same backtracking principles we saw in the whole backtracking series applies here too. The deepest level recursion can go is k so we have O(k) space complexity, while for time complexity we have k decisions to make and maximum of 9 choices which leads us to O(9^k*k) with k multiplier to copy every list that fulfills the above mentioned statements. For the space complexity we have O(k) since we’re dealing with currentList which has at most k elements.

Combination Sum III