subsets.md

78. Subsets - 子集

Tags - 题目标签

Description - 题目描述

EN:

Given an integer array nums of unique elements, 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,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.

ZH-CN:

给你一个整数数组 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 中的所有元素 互不相同

Link - 题目链接

LeetCode - LeetCode-CN

Latest Accepted Submissions - 最近一次 AC 的提交

Language	Runtime	Memory	Submission Time
typescript	56 ms	44.3 MB	2022/06/01 23:03

function subsets(nums: number[]): number[][] {
  if (nums.length === 1) {
    return [[], nums];
  }

  const res = [];

  const backtrack = (path: number[], idx: number) => {
    if (idx === nums.length) {
      res.push([...path]);
      return;
    }
    path.push(nums[idx]);
    backtrack(path, idx + 1);
    path.pop();
    backtrack(path, idx + 1);
  }

  backtrack([], 0);

  return res;
};

My Notes - 我的笔记

思路1：对每一个元素与之前的元素组合：

function subsets(nums: number[]): number[][] {
  if (nums.length === 1) {
    return [[], nums];
  }

  const res = [[]];

  for (let i = 0; i < nums.length; i++) {
    const len = res.length;
    for (let j = 0; j < len; j++) {
      res.push([...res[j], nums[i]]);
    }
  }

  return res;
};

思路2：回溯

C++ 总结了回溯问题类型 带你搞懂回溯算法(大量例题)

上面的链接参考思想即可，代码不要借鉴。

还是参考官方题解的第二种方法写的代码：

function subsets(nums: number[]): number[][] {
  if (nums.length === 1) {
    return [[], nums];
  }

  const res = [];

  const backtrack = (path: number[], idx: number) => {
    if (idx === nums.length) {
      res.push([...path]);
      return;
    }
    path.push(nums[idx]);
    backtrack(path, idx + 1);
    path.pop();
    backtrack(path, idx + 1);
  }

  backtrack([], 0);

  return res;
};

push() 了之后递归，又 pop()了之后再递归，即是考虑当前选项和不考虑当前选项的两种方案。这比把path重新复制一遍性能要好。

但最后找到答案后还是要复制一遍 path 推到 res 中。