AlgoPressAppearance
0090-子集II
https://leetcode.cn/problems/subsets-ii
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
提示：
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
思路
这个问题是 78 子集的加强版，有重复的数组，最后需要排重。
排序，然后记录前一次添加进去的值是什么，记录为 back 变量， 当前一次的值移除后，这次再添加相同的值，就是重复的，需要跳过
实现代码
csharp
public class Solution {
List<IList<int>> result = new List<IList<int>>();
int back = -11;
private void dfs(int[] nums, int begin, List<int> list){
//输出结果
result.Add(new List<int>(list.ToArray()));
//遍历递归
for(int i=begin; i<nums.Length; i++){
if(nums[i] != back){
list.Add(nums[i]);
dfs(nums,i+1,list);
back = list[list.Count - 1];
list.RemoveAt(list.Count-1); //回溯
}
}
}
public IList<IList<int>> SubsetsWithDup(int[] nums) {
List<int> list = new List<int>();
Array.Sort(nums);
dfs(nums,0,list);
return result;
}
}