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

給定一個無重複元素的正整數數組 candidates 和一個正整數 target ，找出 candidates 中所有可以使數字和為目標數 target 的唯一組合。

candidates 中的數字可以無限制重複被選取。如果至少一個所選數字數量不同，則兩種組合是唯一的。 

對於給定的輸入，保證和為 target 的唯一組合數少於 150 個。

---

由於搜尋順序為candidate[i]開始往後搜尋, 因此在做第candidate[i+1]的組合時不用往前確認(因為之前的組合已經被前面的元素檢查過了)。

核心概念為

tmp.push_back(candidates[i]);
dfs(candidates, target-candidates[i], i, tmp, ans);
tmp.pop_back();

先將輪到的元素candidate[i]放進回傳數組中, 然後再度呼叫遞迴函式, 而遞迴函式又會再將candidate[i]放入回傳數組中, 如此反覆直到target=0或是target值小於candidate[i]。此時退出最底層遞迴(如果target=0則須將回傳數組放入答案數組中), 並且pop出回傳數組的最後一個元素(candidate[i]), 然後從candidate[i+1]開始嘗試...直到candidate[n-1]。最後可以得出第一個元素為candidate[i]的所有組合, 然後接續得出第一個元素為candidate[i+1]的所有組合...直到得出所有組合, 迴圈中止。

---

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        vector<int> tmp;
        sort(candidates.begin(), candidates.end());
        dfs(candidates, target, 0, tmp, ans);
        return ans;
    }
    
    void dfs(vector<int>& candidates, int target, int pos, vector<int>& tmp, vector<vector<int>>& ans){
        if(target==0){
            ans.push_back(tmp);
            return;
        }
        for(int i=pos;i<candidates.size();i++){
            if(candidates[i]>target)break;
            tmp.push_back(candidates[i]);
            dfs(candidates, target-candidates[i], i, tmp, ans);
            tmp.pop_back();
        }
    }
};