LC-子集

发表于 更新于 分类于

题目描述

子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

1
2
3
4
5
6
7
8
9
10
11
12
输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

代码实现

注意这段代码里的 res.push(temp.slice())，如果没有 slice() 的话，res 的最后子元素会都是空数组，[ [], [], [], [] ]，原因就是我们传递了一个引用类型值 temp，相当于引用的复制，并且在 dfs 函数中我们对 temp 进行了改变，最后 temp 会变成 []。

在下面这段代码里 temp.pop() 是点睛之笔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
  let result = [];

  function backTracking(temp, index) {
    result.push(temp.slice())
    for (let i = index; i < nums.length; i++) {
      temp.push(nums[i]);
      backTracking(i + 1, temp);
      temp.pop();
    }
  }
  backTracking([], 0);
  return result;
};

下面这段代码中 res.push(temp)，因为我们并没有在 backTracking 函数中改变 temp，而是在参数过程中改变了 temp，其实是利用了 concat。

ES6 …

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
  let result = [];

  function backTracking(temp, index) {
    result.push(temp);
    for (let i = index; i < nums.length; i++) {
      backTracking([...temp, nums[i]], i + 1);
      // backTracking(temp.concat([nums[i]]), i + 1);
    }
  }
  backTracking([], 0);
  return result;
};