LeetCode:40. Combination Sum II

題目大意是由一組數任意組合，使其和等于target，每個數隻能用一次，而且答案不能重複。

題目在第39題上加了每個數字隻能用一次的限制條件。需要對代碼稍作修改。

這裡用了一個isVisited數組來記錄candidates中某個數是否在目前nums中

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> nums;
        vector<bool> isVisited(candidates.size(), false);
        sort(candidates.begin(), candidates.end());
        backtrack(res, nums, candidates, target, 0, isVisited);
        return res;
    }
private:
    void backtrack(vector<vector<int>> &res, vector<int> nums, const vector<int>& cans, int remain, int index, vector<bool>& isVisited) {
        if (remain < 0) return;
        else if (remain == 0) {
            res.push_back(nums);
            return;
        }
        else {
            for (int i = index; i < cans.size(); ++i) {
                if (i > 0 && cans[i] == cans[i-1] && !isVisited[i-1]) continue;//關鍵是這裡的!isVisited[i-1]
                isVisited[i] = true;
                nums.push_back(cans[i]);
                backtrack(res, nums, cans, remain-cans[i], i+1, isVisited);
                nums.pop_back();
                isVisited[i] = false;
            }
        }
    }
};
//isVisited來表示candidates中某個數是否在目前nums中
//難以了解的是這裡的!isVisited[i-1]
//隻有目前數與前一個數相同，并且前一個數不在目前nums裡面，說明的是：前一個數已經被考慮過了，而考慮目前這個數與考慮前一個數的情況是相同的，是以不應該再次考慮目前這個數，必須略過。
           

難以了解的是遞歸調用中的的!isVisited[i-1]：

隻有目前數與前一個數相同，并且前一個數不在目前nums裡面，說明的是：前一個數已經被考慮過了，而考慮目前這個數與考慮前一個數的情況是相同的，是以不應該再次考慮目前這個數，必須略過。

注意一個使用set的方法：

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> ret;
        vector<int> temp;
        sort(candidates.begin(), candidates.end());
        helper(candidates, target, 0, 0, temp, ret);
        return std::move(ret);
    }
private:
    void helper(vector<int>& nums, int target, int idx, int tempSum, vector<int>& temp, vector<vector<int>>& ret) {
        if (tempSum > target)
            return;
        if (tempSum == target) {
            ret.push_back(temp);
            return;
        }
        if (idx == nums.size())
            return;
        unordered_set<int> si;
        for (int i = idx; i < nums.size(); ++i) {
            if (si.find(nums[i]) != si.end())
                continue;
            si.insert(nums[i]);
            temp.push_back(nums[i]);
            helper(nums, target, i+1, tempSum+nums[i], temp, ret);
            temp.pop_back();
        }
    }
};
           

注意的是必須要排序，不然的話會發生元素相同但倒了一下的情況。

另外，既然排序了，不如用第一種used[]的方法。這裡set隻是一個備選項