Combination Sum III

MEDIUM

Description

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

Approaches

Checkout 2 different approaches to solve Combination Sum III. Click on different approaches to view the approach and algorithm in detail.

Brute Force with Nested Loops

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

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 Analysis

Time Complexity: O(9^k) - need to check all possible combinations of k numbers from 1 to 9Space Complexity: O(1) excluding the space needed for output

Pros and Cons

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

Code Solutions

Checking out 5 solutions in different languages for Combination Sum III. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Combination Sum III

Patterns:

Backtracking

Data Structures:

Array