题目
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
示例 1：
输入：nums = [1,2,2] 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：
输入：nums = [0] 输出：[[],[0]]
解题
方法一：回溯
leetcode-78：子集的思路，只不过此题，可以只能用nums里面出现过的数字，每个数字只能用一次
类似leetcode-39：组合总和和leetcode-40：组合总和 II的区别
用的是同一种去重的方式
横向不能重复，纵向可以。
class Solution { public: vector<vector<int>> res; vector<int> path; void backtracing(vector<int>& nums,int startIndex){ res.push_back(path); for(int i=startIndex;i<nums.size();i++){ if(i>startIndex&&nums[i]==nums[i-1]) continue; //去重 path.push_back(nums[i]); backtracing(nums,i+1); path.pop_back(); } } vector<vector<int>> subsetsWithDup(vector<int>& nums) { sort(nums.begin(),nums.end()); backtracing(nums,0); return res; } };
java
class Solution { List<List<Integer>> res=new LinkedList<>(); List<Integer> path=new LinkedList<>(); void dfs(int[] nums,int startIndex,boolean[] used){ res.add(new LinkedList<>(path)); for(int i=startIndex;i<nums.length;i++){ if(i>0&&nums[i]==nums[i-1]&&used[i-1]==false) continue; used[i]=true; path.add(nums[i]); dfs(nums,i+1,used); path.remove(path.size()-1); used[i]=false; } } public List<List<Integer>> subsetsWithDup(int[] nums) { boolean[] used=new boolean[nums.length]; Arrays.sort(nums); dfs(nums,0,used); return res; } }
