子集

题目

LeetCode 第 78 题 子集

题目描述

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

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

示例 1：

输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 示例 2：

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

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素 互不相同

解题思路

回溯法

完整的回溯是全排列，子集则是全排列的一种特殊情况，所以可以使用回溯法来解题，不走回头路即可 全排列 > 全组合 > 全子集

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function (nums) {
  const len = nums.length;
  // 存储结果数组
  const res = [];
  // 每次结果暂存
  const temp = [];
  // 回溯函数 传入每次回溯的起点
  function backtrack(start) {
    // 每次回溯都是子集，push 到结果数组
    res.push([...temp]);
    // 从 start 开始遍历
    for (let i = start; i < len; i++) {
      // 加入结果数组回溯
      temp.push(nums[i]);
      backtrack(i + 1);
      temp.pop();
    }
  }
  backtrack(0);
  return res;
};

迭代解法

集合可以看作二进制的每一位是 1 的集合，一共 2^n - 1 个， 每个 digit 代表 nums 中的一个数, 1 代表包含该数，0 代表不包含该数

var subsets = function(nums) {
    const ans = [];
    const n = nums.length;
    for (let mask = 0; mask < (1 << n); ++mask) {
        const t = [];
        for (let i = 0; i < n; ++i) {
            if (mask & (1 << i)) {
                t.push(nums[i]);
            }
        }
        ans.push(t);
    }
    return ans;
};

总结

• 枚举的方法比较好理解，但是空间复杂度较高
• 回溯的方式需要较多的内存，但是时间复杂度较低
• 如果内存足够用回溯，如果内存不足，可以用迭代