Problem

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.

Examples

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.

Similar Problems

Solution

Method 1 - Backtracking

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

public void helper(List<List<Integer>> ans, List<Integer> subAns, int k, int remain, int start) {
	if (remain<0 || subAns.size() > k) {
		return;
	}

	if (remain == 0 && subAns.size() == k) {
		ans.add(new ArrayList<Integer> (subAns));
		return;
	}

	for (int i = start; i<= 9; i++) {
		subAns.add(i);
		helper(ans, subAns, k, remain - i,  i + 1);
		subAns.remove(subAns.size() - 1);
	}
}

Complexity

  • ⏰ Time complexity: O(9^k), as at each step our recursion tree is splitting into 9 steps
  • 🧺 Space complexity: O(k), assuming recursion stack