子集II（90）

题目

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例

输入：nums = [1,2,2] 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

输入：nums = [0] 输出：[[],[0]]

提示

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10

算法

迭代

方法类似上一题子集（49），不过本题会出现重复元素，所以我们需要用变量duplicateStart来保存当前遍历的起点：当当前数字和上一次课的数字重复时，为了避免重复数字出现，我们用变量duplicateStart保存上一次数字插入的位置，本次遍历只从上一轮新插入res的数字开始；否则仍从0开始

为了保证算法可以有效的去重，我们需要先将nums进行从小到大排序

const subsetsWithDup = nums => {
	nums.sort((a, b) => a - b);
	const res = [[]];
	let duplicateStart = 0;
	for (let i = 0; i < nums.length; i++) {
		const temp = [];
		let j = 0;
		if (i !== 0 && nums[i] === nums[i - 1]) {
			j = duplicateStart;
		}
		for (; j < res.length; j++) {
			temp.push([...res[j], nums[i]]);
		}
		duplicateStart = res.length;
		res.push(...temp);
	}
	return res;
};