给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
- 输入: [1,2,2]
- 输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
做本题之前一定要先做78.子集。
这道题目和78.子集区别就是集合里有重复元素了，而且求取的子集要去重。
那么关于回溯算法中的去重问题，在40.组合总和II中已经详细讲解过了，和本题是一个套路。
剧透一下，后期要讲解的排列问题里去重也是这个套路，所以理解“树层去重”和“树枝去重”非常重要。
用示例中的[1, 2, 2] 来举例，如图所示： （注意去重需要先对集合排序）
从图中可以看出，同一树层上重复取2 就要过滤掉，同一树枝上就可以重复取2，因为同一树枝上元素的集合才是唯一子集！
本题就是其实就是回溯算法：求子集问题！的基础上加上了去重，去重我们在回溯算法：求组合总和（三）也讲过了，所以我就直接给出代码了：
C++代码如下：
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex, vector<bool>& used) {
result.push_back(path);
for (int i = startIndex; i < nums.size(); i++) {
// used[i - 1] == true，说明同一树支candidates[i - 1]使用过
// used[i - 1] == false，说明同一树层candidates[i - 1]使用过
// 而我们要对同一树层使用过的元素进行跳过
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
continue;
}
path.push_back(nums[i]);
used[i] = true;
backtracking(nums, i + 1, used);
used[i] = false;
path.pop_back();
}
}
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
result.clear();
path.clear();
vector<bool> used(nums.size(), false);
sort(nums.begin(), nums.end()); // 去重需要排序
backtracking(nums, 0, used);
return result;
}
};使用set去重的版本。
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex, vector<bool>& used) {
result.push_back(path);
unordered_set<int> uset;
for (int i = startIndex; i < nums.size(); i++) {
if (uset.find(nums[i]) != uset.end()) {
continue;
}
uset.insert(nums[i]);
path.push_back(nums[i]);
backtracking(nums, i + 1, used);
path.pop_back();
}
}
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
result.clear();
path.clear();
vector<bool> used(nums.size(), false);
sort(nums.begin(), nums.end()); // 去重需要排序
backtracking(nums, 0, used);
return result;
}
};本题也可以不适用used数组来去重，因为递归的时候下一个startIndex是i+1而不是0。
如果要是全排列的话，每次要从0开始遍历，为了跳过已入栈的元素，需要使用used。
代码如下：
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex) {
result.push_back(path);
for (int i = startIndex; i < nums.size(); i++) {
// 而我们要对同一树层使用过的元素进行跳过
if (i > startIndex && nums[i] == nums[i - 1] ) { // 注意这里使用i > startIndex
continue;
}
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
result.clear();
path.clear();
sort(nums.begin(), nums.end()); // 去重需要排序
backtracking(nums, 0);
return result;
}
};其实这道题目的知识点，我们之前都讲过了，如果之前讲过的子集问题和去重问题都掌握的好，这道题目应该分分钟AC。
当然本题去重的逻辑，也可以这么写
if (i > startIndex && nums[i] == nums[i - 1] ) {
continue;
}
class Solution {
List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
boolean[] used;
public List<List<Integer>> subsetsWithDup(int[] nums) {
if (nums.length == 0){
result.add(path);
return result;
}
Arrays.sort(nums);
used = new boolean[nums.length];
subsetsWithDupHelper(nums, 0);
return result;
}
private void subsetsWithDupHelper(int[] nums, int startIndex){
result.add(new ArrayList<>(path));
if (startIndex >= nums.length){
return;
}
for (int i = startIndex; i < nums.length; i++){
if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]){
continue;
}
path.add(nums[i]);
used[i] = true;
subsetsWithDupHelper(nums, i + 1);
path.removeLast();
used[i] = false;
}
}
}class Solution:
def __init__(self):
self.paths = []
self.path = []
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
nums.sort()
self.backtracking(nums, 0)
return self.paths
def backtracking(self, nums: List[int], start_index: int) -> None:
# ps.空集合仍符合要求
self.paths.append(self.path[:])
# Base Case
if start_index == len(nums):
return
# 单层递归逻辑
for i in range(start_index, len(nums)):
if i > start_index and nums[i] == nums[i-1]:
# 当前后元素值相同时，跳入下一个循环，去重
continue
self.path.append(nums[i])
self.backtracking(nums, i+1)
self.path.pop()var res[][]int
func subsetsWithDup(nums []int)[][]int {
res=make([][]int,0)
sort.Ints(nums)
dfs([]int{},nums,0)
return res
}
func dfs(temp, num []int, start int) {
tmp:=make([]int,len(temp))
copy(tmp,temp)
res=append(res,tmp)
for i:=start;i<len(num);i++{
if i>start&&num[i]==num[i-1]{
continue
}
temp=append(temp,num[i])
dfs(temp,num,i+1)
temp=temp[:len(temp)-1]
}
}var subsetsWithDup = function(nums) {
let result = []
let path = []
let sortNums = nums.sort((a, b) => {
return a - b
})
function backtracing(startIndex, sortNums) {
result.push(path.slice(0))
if(startIndex > nums.length - 1) {
return
}
for(let i = startIndex; i < nums.length; i++) {
if(i > startIndex && nums[i] === nums[i - 1]) {
continue
}
path.push(nums[i])
backtracing(i + 1, sortNums)
path.pop()
}
}
backtracing(0, sortNums)
return result
};int* path;
int pathTop;
int** ans;
int ansTop;
//负责存放二维数组中每个数组的长度
int* lengths;
//快排cmp函数
int cmp(const void* a, const void* b) {
return *((int*)a) - *((int*)b);
}
//复制函数，将当前path中的元素复制到ans中。同时记录path长度
void copy() {
int* tempPath = (int*)malloc(sizeof(int) * pathTop);
int i;
for(i = 0; i < pathTop; i++) {
tempPath[i] = path[i];
}
ans = (int**)realloc(ans, sizeof(int*) * (ansTop + 1));
lengths[ansTop] = pathTop;
ans[ansTop++] = tempPath;
}
void backTracking(int* nums, int numsSize, int startIndex, int* used) {
//首先将当前path复制
copy();
//若startIndex大于数组最后一位元素的位置，返回
if(startIndex >= numsSize)
return ;
int i;
for(i = startIndex; i < numsSize; i++) {
//对同一树层使用过的元素进行跳过
if(i > 0 && nums[i] == nums[i-1] && used[i-1] == false)
continue;
path[pathTop++] = nums[i];
used[i] = true;
backTracking(nums, numsSize, i + 1, used);
used[i] = false;
pathTop--;
}
}
int** subsetsWithDup(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
//声明辅助变量
path = (int*)malloc(sizeof(int) * numsSize);
ans = (int**)malloc(0);
lengths = (int*)malloc(sizeof(int) * 1500);
int* used = (int*)malloc(sizeof(int) * numsSize);
pathTop = ansTop = 0;
//排序后查重才能生效
qsort(nums, numsSize, sizeof(int), cmp);
backTracking(nums, numsSize, 0, used);
//设置一维数组和二维数组的返回大小
*returnSize = ansTop;
*returnColumnSizes = (int*)malloc(sizeof(int) * ansTop);
int i;
for(i = 0; i < ansTop; i++) {
(*returnColumnSizes)[i] = lengths[i];
}
return ans;
}
