# LC 216. Combination Sum III

### [Problem link](https://leetcode.com/problems/combination-sum-iii/)

###### tags: `leedcode` `medium` `python` `c++` `Backtracking`

Find all valid combinations of <code>k</code> numbers that sum up to <code>n</code> such that the following conditions are true:

- Only numbers <code>1</code> through <code>9</code> 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:**

- <code>2 <= k <= 9</code>
- <code>1 <= n <= 60</code>

## Solution 1
#### Python

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        self.res = []
        self.path = []

        def backtrack(startIdx, tmp_sum):
            if tmp_sum > n: # pruning
                return
            if len(self.path) == k:
                if tmp_sum == n:
                    self.res.append(self.path[:])
                return
            
            endIdx = 10 - (k - len(self.path))
            for i in range(startIdx, endIdx + 1):   # pruning
                self.path.append(i)
                tmp_sum += i
                backtrack(i + 1, tmp_sum)
                self.path.pop()
                tmp_sum -= i

        backtrack(1, 0)

        return self.res

#### C++

class Solution {
public:
    vector<vector<int>> res;

    void backtracking(int k, int n, vector<int> &path, int &pathSum, int startIdx) {
        if (path.size() == k) {
            if (pathSum == n) {
                res.push_back(path);
            }
            return;
        }
        for (int i = startIdx; i <= 9 - (k - path.size()) + 1; i++) {
            path.push_back(i);
            pathSum += i;
            backtracking(k, n, path, pathSum, i + 1);
            path.pop_back();
            pathSum -= i;
        }
    }

    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int> path;
        int pathSum = 0;
        backtracking(k, n, path, pathSum, 1);
        return res;
    }
};

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int> path;
        int pathSum = 0;
        vector<vector<int>> ans;

        function<void(int)> dfs = [&](int i) {
            if (path.size() == k) {
                if (pathSum == n) {
                    ans.push_back(path);
                }
                return;
            }
            for (int j = i; j <= 9 - (k - path.size()); j++) {
                path.push_back(j + 1);
                pathSum += j + 1;
                dfs(j + 1);
                path.pop_back();
                pathSum -= j + 1;
            }
        };
        dfs(0);
        return ans;
    }
};

>### Complexity
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(n * 2^n) | O(n) |

## Note
x