Combination Sum III
MedPrompt
Find all valid combinations of k numbers that sum up to n such that the following conditions are true:
- Only numbers
1through9are 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 <= 91 <= n <= 60
Approaches
2 approaches with complexity analysis and trade-offs.
Generate all possible combinations of k numbers from 1 to 9 using nested loops and check if their sum equals n.
Algorithm
- Use k nested loops to iterate from 1 to 9
- For each combination of k numbers:
- Calculate their sum
- If sum equals n, add the combination to result
- Return all valid combinations
Walkthrough
This approach uses nested loops to generate all possible combinations of k numbers from 1 to 9. For each combination, we check if the sum equals the target n and if each number is used only once.
public List<List<Integer>> combinationSum3(int k, int n) { List<List<Integer>> result = new ArrayList<>(); // Generate combinations using nested loops for (int i = 1; i <= 9; i++) { for (int j = i + 1; j <= 9; j++) { for (int l = j + 1; l <= 9; l++) { // Example for k = 3 if (k == 3 && i + j + l == n) { result.add(Arrays.asList(i, j, l)); } } } } return result;}This implementation shows an example for k=3. For different values of k, we would need different number of nested loops, making it impractical for larger values of k.
Complexity
Time
O(9^k) - need to check all possible combinations of k numbers from 1 to 9
Space
O(1) excluding the space needed for output
Trade-offs
Pros
Simple to understand and implement for small values of k
No extra space required except for storing results
Cons
Very inefficient for larger values of k
Requires hardcoding loops based on k
Not flexible for different values of k
Solutions
Solution
public class Solution { private List < IList < int >> ans = new List < IList < int >>(); private List < int > t = new List < int >(); private int k ; public IList < IList < int >> CombinationSum3 ( int k , int n ) { this . k = k ; dfs ( 1 , n ); return ans ; } private void dfs ( int i , int s ) { if ( s == 0 ) { if ( t . Count == k ) { ans . Add ( new List < int >( t )); } return ; } if ( i > 9 || i > s || t . Count >= k ) { return ; } t . Add ( i ); dfs ( i + 1 , s - i ); t . RemoveAt ( t . Count - 1 ); dfs ( i + 1 , s ); } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.