Description:
https://leetcode.com/problems/subsets-ii/#/description
Algorithm for 90. Subsets II:
Solution1:
Solution1 is similar to the solution of 78. Subsets. There are two choices: add the number to answer or not.
The key point is to sort the input, then sort + erase unique for the final answer.
Remeber: unique() only remove the adjacent duplicate elements. To remove all the duplicates, sort() must be applied to the vector.
Solution2:
Use for loop in the DFS function.
Code1:
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> result;
vector<int>path;
helper(nums, path, 0, result);
result.erase(unique(result.begin(), result.end()), result.end());
result.erase(unique(result.begin(), result.end()), result.end());
return result;
}
private:
void helper(vector<int> &nums, vector<int> &path, int step, vector<vector<int>> &result)
{
if (step == nums.size())
{
result.push_back(path);
return;
}
helper(nums, path, step + 1, result);
path.push_back(nums[step]);
helper(nums, path, step + 1, result);
path.pop_back();
}
};
Code2:
class Solution2 {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
vector<int>path;
result.push_back({});
helper(nums, path, 0, result);
return result;
}
private:
void helper(vector<int> &nums, vector<int> &path, int step, vector<vector<int>> &result)
{
for (int i = step; i < nums.size();i++)
{
if (i > step && nums[i] == nums[i - 1])
continue;
path.push_back(nums[i]);
result.push_back(path);
helper(nums, path, i + 1, result);
path.pop_back();
}
}
};
Timing: