# 40 - Combination Sum II

解法一 - Backtracking

這題跟 # 39 - Combination Sum 只差在同樣的 element 不能重複用，所以實作上的一個重大差別就是：

1. 在呼叫 recursive function 的時候，必須要從下一個 index 繼續往後搜尋。

2. 為了避免對重複開頭的 state 搜尋，我們加上了一行判斷：

   if(i>begin && candidates[i] == candidates[i-1]) continue;

實作如下：

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> sol;
        vector<int> state;

        sort(candidates.begin(), candidates.end());
        helper(candidates, target, sol, state, 0);

        return sol;
    }

private:
    void helper(vector<int>& candidates, int target, vector<vector<int>>& sol, vector<int> state, int begin) {
        if(target == 0) {
            sol.push_back(state);
        }
        else if(target < 0) {
            return;
        }
        else {
            for(int i=begin; i<candidates.size(); i++) {
                // Prevent searching for same starting state
                // e.g. candidates = [1,1,2,5,6,7,10]
                // in the beginning, we will search goal states containing first 1
                // when the search containing first 1 ends
                // we already have [1,1,6], [1,2,5], [1,7] in sol
                // Now begin goes to 1
                // we don't want to search goal states containing 1 one more time
                // so we just pass this search 
                if(i>begin && candidates[i] == candidates[i-1]) continue;
                state.push_back(candidates[i]);
                helper(candidates, target-candidates[i], sol, state, i+1);
                state.pop_back();
            }
        }
    }
};