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

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

The same repeated number may be chosen from candidates unlimited number of times.

Note:

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

EX:

        Input: candidates = [2,3,5], target = 8,

    A solution set is:
    [
      [2,2,2,2],
      [2,3,3],
      [3,5]
    ]

想法:

     這題就是用 DFS 去列舉可能的組合，比較需要注意的是如何去除重複的解？ 這邊提供兩種作法，第一種方法是我們

利用一個 HashMap 紀錄 candidates 中出現的數，然後按照 1 ~ target 的順序做列舉，用 HashMap 可以快速判斷

當前數字是否在 candidates 中，按照順序列舉的好處就是找到的解會是排序好的，因此就不會有重複的情形發生，例如

[2,3,3] 這組解就不會列舉出 [2,3,2]之類的多餘的解。第二種作法跟第一種作法概念類似，只不過我們在列舉前先對 candidates

進行排序，如此便可以按照大小順序列舉 candidates 中的數因此能確保找到的解也是排序好的，從而避免產生重複的解。

完整程式碼:

解法一(HashMap):

class Solution {
public:
    vector<vector<int>> ans;
    void dfs(vector<int>& candidates, vector<int>& cur, unordered_set<int>& s, int target) {
        if (target == 0) {
            ans.emplace_back(cur);
            return;
        }
        // avoid duplicate solution, if no k, all recursive start from 1, then that is permutation
        auto k = cur.empty()? 1 : cur.back();
        for (int i = k; i <= target; i++) {
            if (s.find(i) != s.end()) {
                cur.emplace_back(i);
                dfs(candidates, cur, s, target - i);
                cur.pop_back();
            }
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> cur;
        unordered_set<int> s(candidates.begin(), candidates.end());
        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; }
            cur.emplace_back(candidates[i]);
            dfs(candidates, cur, i, target - candidates[i]);
            cur.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<int> cur;
        //unordered_set<int> s(candidates.begin(), candidates.end());
        // we sort candidates first, so we do not need to find element in set as previous solution
	sort(candidates.begin(), candidates.end());
        dfs(candidates, cur, 0, target);
        return ans;
    }
};