# Combination Sum III
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/combination-sum-iii)
Canonical: https://scaleengineer.com/dsa/problems/combination-sum-iii
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Data structures:** Array
---
## 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.

**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
## 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.
**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
**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
### Explanation
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.

```java
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.
### Algorithm
1. Use k nested loops to iterate from 1 to 9
2. For each combination of k numbers:
   - Calculate their sum
   - If sum equals n, add the combination to result
3. Return all valid combinations

## Backtracking with Recursion
Use backtracking to generate combinations by making choices at each step and undoing them if they don't lead to a valid solution.
**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
**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
### Explanation
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.

```java
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.
### Algorithm
1. Start with an empty combination
2. 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
3. When k numbers are selected and sum equals n, add to result

# Solutions
### CSharp

```csharp
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 ); } }
```

### Java

```java
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);
  }
}

```

### JavaScript

```javascript
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 ; }
```

### Python

```python
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):

```

### CPP

```cpp
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;
  }
};

```