LeetCode 40. Combination Sum II [Medium] [C++] 解題筆記

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

EX:

        Input: candidates = [10,1,2,7,6,1,5], target = 8,

    A solution set is:
    [
      [1, 7],
      [1, 2, 5],
      [2, 6],
      [1, 1, 6]
    ]

想法:

    這題與 39. Combination Sum 類似，差別在於 39 題中每個數字可以重複使用，而這題不行，因此這題可以

使用與 39 中提到的兩種方式只是要在列舉時判斷該元素是否使用過了即可。

    另外這題還有一種作弊的方式就是使用 set 來儲存答案，這樣根據　set 的特性它本身就會將多餘的解刪除了，

就不用再額外做處理。

完整程式碼:

解法一(HashMap):

class Solution {
public:
    vector<vector<int>> ans;
    void dfs(vector<int>& candidates, vector<int>& cur, unordered_map<int,int>& s, int target) {
        if (target == 0) {
            ans.emplace_back(cur);
            return;
        }
        auto k = cur.empty()? 1 : cur.back();
        for (int i = k; i <= target; i++) {
            if (s.find(i) == s.end()) { continue; }
            if (s[i] == 0) { continue; }
            s[i]--;
            cur.emplace_back(i);
            dfs(candidates, cur, s, target - i);
            cur.pop_back();
            s[i]++;
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
            unordered_map<int,int> s;
            for (int i = 0; i < candidates.size(); i++) {
                s[candidates[i]]++;
            }
            vector<int> cur;
            dfs(candidates, cur, s, target);
        
            return ans;
    }
};

解法二(sorting):

class Solution {
public:
    vector<vector<int>> ans;
    void dfs(vector<int>& candidates, vector<int>& cur, int deep, int target) {
        if (target == 0) {
            ans.emplace_back(cur);
            return;
        }
        for (int i = deep; i < candidates.size(); i++) {
            if (candidates[i] > target) { return; }
            // same element can only use once in each search level to avoid duplicate result
            if (i > deep && candidates[i] == candidates[i-1]) { continue; }
            cur.emplace_back(candidates[i]);
            dfs(candidates, cur, i + 1, target - candidates[i]);
            cur.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
            sort(candidates.begin(), candidates.end());
            vector<int> cur;
            dfs(candidates, cur, 0, target);
        
            return ans;
    }
};

解法三(cheat solution):

class Solution {
public:
    set<vector<int>> cheat_ans;
    void dfs(vector<int>& candidates, vector<int>& cur, int deep, int target) {
        if (target == 0) {
            cheat_ans.insert(cur);
            return;
        }
        for (int i = deep; i < candidates.size(); i++) {
            if (candidates[i] > target) { return; }
            cur.emplace_back(candidates[i]);
            dfs(candidates, cur, i + 1, target - candidates[i]);
            cur.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
            sort(candidates.begin(), candidates.end());
            vector<int> cur;
            dfs(candidates, cur, 0, target);
            
            return vector<vector<int>>(cheat_ans.begin(), cheat_ans.end()) ;
    }
};