问题描述:
给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明:解集不能包含重复的子集。
题目解析:
本题的主要解题算法还是回溯算法,但要注意处理重复子集的问题。即应该对相同元素实行跳过。
class Solution {
public:
void dfs(vector<int>& nums, vector<vector<int>>& result, vector<int>& list, vector<int>& visted, int pos) {
if (pos==nums.size())
{
result.push_back(list);
return;
}
if (pos == 0 || nums[pos-1] != nums[pos] || visted[pos-1]) {//选以及选的条件
list.push_back(nums[pos]);
visted[pos] = 1;
dfs(nums, result, list, visted, pos + 1);
visted[pos] = 0;
list.pop_back();
}
dfs(nums, result, list, visted, pos + 1);//不选
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> result;
vector<int> list;
vector<int> visted(nums.size(),0);
dfs(nums, result, list, visted, 0);
return result;
}
};