78. 子集

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

题目

Given an integer array nums of unique elements, return all possiblesubsets (the power set).

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

Example 1:

Input: nums = [1,2,3]

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

Example 2:

Input: nums = [0]

Output: [[],[0]]

Constraints:

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• All the numbers of nums are unique.

题目大意

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

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

解题思路

可以使用回溯算法，通过递归函数实现:

1. 定义一个结果集 res 用于存储所有的子集。
2. 定义一个辅助数组 track 用于记录当前回溯路径上的元素。
3. 编写回溯算法的核心函数 backtrack，其中参数 start 控制遍历树枝的起始位置，避免产生重复的子集。
4. 在 backtrack 函数中，首先将当前路径 track 加入结果集 res，这表示当前的 track 是一个有效的子集。
5. 然后使用循环遍历从 start 到数组末尾的元素，对于每个元素，做出选择（将其加入 track），然后递归调用 backtrack 进入下一层。
6. 在递归调用返回后，需要撤销选择，即将 track 的末尾元素弹出，以便进行下一次选择。
7. 通过回溯的过程，可以遍历所有可能的子集。

复杂度分析

• 时间复杂度：O(2^n * n)，其中 n 是数组 nums 的长度。这是因为对于每个元素，都有两种选择：选择或不选择，所以总共有 2^n 种可能的子集。在每个选择中，都需要花费 O(n) 的时间来复制当前的路径。

• 空间复杂度：O(2^n * k)

  • 空间复杂度主要取决于递归调用的栈空间和存储结果集的空间。
  • 递归调用栈的最大深度是数组 nums 的长度，所以空间复杂度是 O(n)。
  • 此外，存储结果集的空间复杂度为 O(总子集个数 * 平均子集大小)。在这里，总子集个数为 2^n，平均子集大小为 k（题目要求生成大小为 k 的子集），因此空间复杂度为 O(2^n * k)。
  • 综合考虑以上两部分，整体的空间复杂度为 O(n + 2^n * k)。
  • 在一般情况下，由于 2^n 的增长速度较大，因此空间复杂度可以近似表示为 O(2^n * k)。

代码

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function (nums) {
	// 用于存储结果
	const res = [];
	// 用于记录回溯路径
	const track = [];

	const backtrack = (start) => {
		// 前序遍历位置，每个节点的值都是一个子集
		res.push([...track]);

		// 回溯算法标准框架
		for (let i = start; i < nums.length; i++) {
			// 做选择
			track.push(nums[i]);
			// 回溯遍历下一层节点
			backtrack(i + 1);
			// 撤销选择
			track.pop();
		}
	};

	backtrack(0);
	return res;
};

相关题目

题号	标题	题解	标签	难度
90	子集 II	[✓]	位运算 数组 回溯
320	列举单词的全部缩写 🔒		位运算 字符串 回溯
784	字母大小写全排列		位运算 字符串 回溯
1982	从子集的和还原数组		数组 分治
2044	统计按位或能得到最大值的子集数目	[✓]	位运算 数组 回溯 1+