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
Use backtracking to generate combinations by making choices at each step and undoing them if they don't lead to a valid solution.
Algorithm
- Start with an empty combination
- For each position:
- Try numbers from 1 to 9 that haven't been used
- Add number to current combination
- Recursively try to complete the combination
- Remove number (backtrack) if combination isn't valid
- When k numbers are selected and sum equals n, add to result
Walkthrough
This approach uses backtracking to systematically explore all possible combinations. We maintain a current combination and add numbers one by one. When we reach k numbers and their sum equals n, we've found a valid combination.
public List<List<Integer>> combinationSum3(int k, int n) { List<List<Integer>> result = new ArrayList<>(); backtrack(result, new ArrayList<>(), k, n, 1); return result;} private void backtrack(List<List<Integer>> result, List<Integer> current, int k, int remain, int start) { if (current.size() == k && remain == 0) { result.add(new ArrayList<>(current)); return; } if (current.size() >= k || remain <= 0) { return; } for (int i = start; i <= 9; i++) { current.add(i); backtrack(result, current, k, remain - i, i + 1); current.remove(current.size() - 1); }}The backtracking function maintains the current state and explores possibilities by adding numbers and removing them when backtracking.
Complexity
Time
O(C(9,k)) - where C(9,k) is the binomial coefficient, representing possible combinations of k numbers from 9 numbers
Space
O(k) for recursion stack depth
Trade-offs
Pros
More efficient than brute force approach
Works for any value of k
Systematically explores all possibilities
Avoids duplicate combinations
Cons
Requires understanding of backtracking concept
Uses recursive calls which can be memory-intensive for large 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 ); } }class Solution {private List<List<Integer>> ans = new ArrayList<>();private List<Integer> t = new ArrayList<>();private int k;public List<List<Integer>> 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.size() == k) { ans.add(new ArrayList<>(t)); } return; } if (i > 9 || i > s || t.size() >= k) { return; } t.add(i); dfs(i + 1, s - i); t.remove(t.size() - 1); dfs(i + 1, s); }}function combinationSum3 ( k , n ) { const ans = []; const t = []; const dfs = ( i , s ) => { if ( s === 0 ) { if ( t . length === k ) { ans . push ( t . slice ()); } return ; } if ( i > 9 || i > s || t . length >= k ) { return ; } t . push ( i ); dfs ( i + 1 , s - i ); t . pop (); dfs ( i + 1 , s ); }; dfs ( 1 , n ); return ans ; }class Solution: # s: sum, t: list if s > n or len ( t ) > k : return if s == n and len ( t ) == k : ans . append ( t . copy ()) return for i in range ( start , 10 ): t . append ( i ) dfs ( i + 1 , s + i , t ) t . pop () ans = [] dfs ( 1 , 0 , []) return ans def combinationSum3(self, k: int, n: int) -> List[List[int]]: def dfs(start, s, t):class Solution {public: vector<vector<int>> combinationSum3(int k, int n) { vector<vector<int>> ans; vector<int> t; function<void(int, int)> dfs = [&](int i, int s) { if (s == 0) { if (t.size() == k) { ans.emplace_back(t); } return; } if (i > 9 || i > s || t.size() >= k) { return; } t.emplace_back(i); dfs(i + 1, s - i); t.pop_back(); dfs(i + 1, s); }; dfs(1, n); return ans; }};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.