###### tags: `Leetcode` `medium` `backtracking` `python` `c++`

# 216. Combination Sum III

## [題目連結:] https://leetcode.com/problems/combination-sum-iii/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.

## 解題想法:
* 此題為
* 給n表示總和
* k表示可以使用的數量
* **求1~9之中，任意k個數字和為n**
* 當前k個數字之中每個數字只能用一次

* 遞迴求解:
* dfs(startNum,k,target,path):
* startNum起始為1~9
* 當前path能裝k個數量
* target為目標和

## Python:

class Solution(object):
    def combinationSum3(self, k, n):
        """
        :type k: int 可以用k個數量
        :type n: int 和為n
        :rtype: List[List[int]]
        """
        if not k or not n:
            return []
        if k>9:
            return []
        self.res=[]
        self.dfs(1,k,n,[])
        return self.res
    
    def dfs(self,startNum,k,target,path):
        #沒扣打了
        if k==0:
            if target==0:
                #要用list()新copy一條path 以面path算是共用變數內容又被改
                self.res.append(list(path))
            return
        for i in range(startNum,10):
            #若start_num已經大於target了 後面也不用看了
            if i>target:
                return
            path.append(i)
            self.dfs(i+1,k-1,target-i,path)
            path.pop()
        return

result= Solution()
k = 3
n = 9
ans = result.combinationSum3(k,n)
print(ans)

## C++:

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        if (k==0 || n==0)
            return res;
        if (k>9)
            return res;
        vector<int> path;
        dfs(1,k,n,path);
        return res;
    }

    void dfs(int startNum, int k, int target, vector<int>& curPath){
        if (k==0){
            if (target==0)
                res.push_back(curPath);
            return;
        }
        for (int i=startNum; i<=9; i++){
            if (i>target)
                return;
            curPath.push_back(i);
            dfs(i+1, k-1, target-i,curPath);
            curPath.pop_back();
        }
    }
private:
    vector<vector<int>> res;
};