90. 子集 II

🟠   🔖  位运算 数组 回溯  🔗 力扣 LeetCode

题目

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

Input: nums = [1,2,2]

Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

Example 2:

Input: nums = [0]

Output: [[],[0]]

Constraints:

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

题目大意

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

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

解题思路

可以使用回溯算法来生成所有可能的子集，并在生成过程中进行去重：

1. 首先对输入的数组 nums 进行排序，以便在后续的去重步骤中方便比较相邻的元素。
2. 定义一个空数组 res 用于存储最终的结果，以及一个空数组 track 用于回溯过程中记录当前的路径。
3. 创建一个名为 backtrack 的递归函数，该函数接受一个参数 start 表示当前遍历的起始位置。
4. 在 backtrack 函数中，首先将当前的路径 track 加入到结果数组 res 中，表示找到了一个新的子集。
5. 然后从 start 开始遍历数组 nums，对于每个元素：
   • 如果当前元素与前一个元素相同（即出现了重复元素），并且当前元素不是起始位置的元素，则跳过当前元素，以避免重复生成相同的子集。
   • 否则，将当前元素加入到路径 track 中，递归调用 backtrack 函数，并传入下一个位置 i + 1 作为参数，以继续生成下一个元素的子集。
   • 在递归调用结束后，需要将当前元素从路径 track 中弹出，以便回溯到上一层继续遍历其他元素。
6. 最后返回结果数组 res。

代码

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function (nums) {
	let res = [];
	let track = [];

	// 排序，以便在后续的步骤中去重
	nums.sort((a, b) => a - b);

	const backtrack = (start) => {
		res.push([...track]);

		for (let i = start; i < nums.length; i++) {
			// 出现了重复元素，跳过
			if (i > start && nums[i] == nums[i - 1]) {
				continue;
			}
			track.push(nums[i]);
			backtrack(i + 1);
			track.pop();
		}
	};

	backtrack(0);
	return res;
};

相关题目

题号	标题	题解	标签	难度
78	子集	[✓]	位运算 数组 回溯
1982	从子集的和还原数组		数组 分治