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

給定一個數組 candidates 和一個目標數 target ，找出 candidates 中所有可以使數字和為 target 的組合。

candidates 中的每個數字在每個組合中只能使用一次。

注意：解集不能包含重複的組合。

---
這題與#39的差別在於每個數字只能用一次, 而且輸入中可能有重複的值, 所以需要做的 :
1. 尋找解時要從現在數的下一個位置的數開始找
2. 檢查重複機制, 可以容許組合裡有重複的值, 但不能容許有重複的組合(代表不能有不同位置但相同的值作為組合的開頭)
3. 不檢查重複輸入, 最後一次刪除答案數組中的重複組合理論上正確, 但遇到特別噁心的輸入時會超時

---

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<int> tmp;
        vector<vector<int>> ans;
        sort(candidates.begin(), candidates.end());
        dfs(candidates, target, 0, tmp, ans);
        
        //這兩行抵擋不了噁心輸入
        //sort(ans.begin(), ans.end()); 要erase前需要先sort
        //ans.erase(unique(ans.begin(), ans.end()), ans.end());
        
        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[pos]>target)return;
            if(i&&i>pos&&candidates[i]==candidates[i-1])continue;// <-檢查重複
            tmp.push_back(candidates[i]);
            dfs(candidates, target-candidates[i], i+1, tmp, ans);
            tmp.pop_back();
        }
    }
};