Subsets II -1.png

Subsets II -2.png

===================== 解題思路 =====================

基本做法與 Subsets 相同 只是在資料進入 subset 時優先檢查是否已經使用過當前的資料, 在做這項檢查時務必加入一個條件
＊當前這項資料不能是 for loop 的第一個資料 否則會減少一次把重複的值推入的條件
另一件非常重要的事情經常忘記, 在開始 DFS 以前必須要先 sort 過題目給的 vector!

===================== C++ code ====================

<pre><code>
class Solution {

public:

/**
 * @param S: A set of numbers.
 * @return: A list of lists. All valid subsets.
 */
vector<vector<int>> subsetsWithDup(vector<int> &S) {
    // write your code here
    vector<vector<int>> res;
    vector<int> sub;
    sort(S.begin(), S.end());
    backtrack(res, sub, 0, S);
    return res;
}

void backtrack(vector<vector<int>> &res, vector<int> &sub, int start, vector<int> &S)
{
    res.emplace_back(sub);
    for(int i = start; i < S.size(); i++)
    {
        if(i != start && S[i] == S[i-1]) continue;
        sub.emplace_back(S[i]);
        backtrack(res, sub, i + 1, S);
        sub.pop_back();
    }
}

};
<code><pre>