子集

题目

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:

输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

解法1 - 回溯法

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function (nums) {
  var res = [];
  var n = nums.length;

  function helper(i, temp) {
    res.push(temp);
    for (var j = i; j < n; j++) {
      helper(j+1, temp.concat(nums[j]));  
    }
  }

  helper(0, []);

  return res;
};

console.log(subsets([1,2,3]))

解法2 - 迭代解法

遍历数组遇到一个数就把所有子集加上该数组成新的子集，遍历完毕即是所有子集。
时间复杂度：O(2^N)
空间复杂度：O(2^N)

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function (nums) {
  var res = [];
  res.push([]);
  for (var i = 0; i < nums.length; i++) {
    var temp = [];
    for (var j = 0; j < res.length; j++) {
      temp.push(res[j].concat(nums[i]));
    }
    res = res.concat(temp);
  }

  return res;
};

console.log(subsets([1,2,3]))