###### tags: `LeetCode` `Medium` `DFS` `Recursion`
# LeetCode #216 [Combination Sum III](https://leetcode.com/problems/combination-sum-iii/)
### (Medium)

找出總和為 n 且滿足以下條件的 k 個數字的所有有效組合：

* 僅使用數字 1 到 9。
* 每個號碼最多使用一次。
* 返回所有可能的有效組合的列表。 該列表不得包含兩次相同的組合，並且可以以任何順序返回這些組合。

---

終止條件為, 個數(k)歸零, 並且數字總和剛好為目標數(n), 此時將暫存數組存入答案數組中。

而若上述條件中僅達成一者, 則不做其他動作, 直接返回(失敗了)。

而因為不得使用重複數, 因此遞迴呼叫時的起始搜尋值為當前數的下一個數(i+1)。

---

class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        //k: numbers n:target
        if(!n)return {};
        vector<int> tmp;
        vector<vector<int>> ans;
        dfs(tmp, k, n, ans, 1);
        return ans;
    }
    void dfs(vector<int>& tmp, int nums, int target, vector<vector<int>>& ans, int pos){
        if(nums==0&&target==0){
            ans.push_back(tmp);
            return;
        }
        else if(target==0||nums==0)return;
        for(int i=pos;i<=9;i++){
            tmp.push_back(i);
            dfs(tmp, nums-1, target-i, ans, i+1);
            tmp.pop_back();
        }
    }
};