Subsets II -1.png
Subsets II -2.png
===================== 解題思路 =====================
基本做法與 Subsets 相同 只是在資料進(jìn)入 subset 時(shí)優(yōu)先檢查是否已經(jīng)使用過當(dāng)前的資料, 在做這項(xiàng)檢查時(shí)務(wù)必加入一個(gè)條件
＊當(dāng)前這項(xiàng)資料不能是 for loop 的第一個(gè)資料 否則會(huì)減少一次把重複的值推入的條件
另一件非常重要的事情經(jīng)常忘記, 在開始 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>
