WEI-CHENG CHEN

說明

跟 39 的不同：

• 每個數字只能使用一次
• 不能有重複的組合

解法

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

        sort(candidates.begin(), candidates.end()); // 一定要排序
        vector<vector<int>> ans;
        vector<int> temp;
        backtracking(ans, temp, candidates, target, 0);
        return ans;

    }

    void backtracking(vector<vector<int>> &ans, vector<int> &temp, vector<int>& candidates, int target, int start){

        // 終止條件
        if(target==0){
            ans.push_back(temp);
            return;
        }
        if(target<0) return;

        for(int i=start;i<candidates.size();i++){
            // 跳過同一層遞迴中出現的重複元素
            if(i>start && candidates[i]==candidates[i-1]) continue;
            temp.push_back(candidates[i]);
            backtracking(ans, temp, candidates, target - candidates[i], i + 1);
            temp.pop_back();
        }
    }
};