78. 子集 (opens new window)

Description

Difficulty: 中等

Related Topics: 位运算 (opens new window), 数组 (opens new window), 回溯 (opens new window)

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

Solution

Language: JavaScript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
// help方法传入一个数组和索引，递归到下一个索引前，要么保持原样，要么push当前索引的值，push后记得pop还原
var subsets = function(nums) {
 let res = [], len = nums.length
 let help = (arr, x) => {
  if (x === len) {
   res.push([...arr])
   return
  }
  // 保持原样，索引加一继续递归
  help(arr, x + 1)
  // push 当前索引的值，索引加一继续递归
  arr.push(nums[x])
  help(arr, x + 1)
  // push 后递归完，pop还原
  arr.pop()
 }
 help([], 0)
 return res
};

var subsets = function (nums) {
 let ret = []
 let path = []

 backtrack(0)
 return ret

 function backtrack (startIndex) {
  ret.push([...path])
  for (let i = startIndex; i < nums.length; i++) {
   const num = nums[i]
   path.push(num)
   backtrack(i+1)
   path.pop()
  }
 }
}