题目

题目来源：力扣（LeetCode）

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

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

思路分析

回溯

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number[][]}
  4.  */
  5. var subsets = function (nums) {
  6.   const t = []; // 子集
  7.   const ans = []; 
  8.   const dfs = (cur) => {
  9.     if (cur === nums.length) { // 指针越界 
  10.       ans.push(t.slice());   // 将当前子集加入解集
  11.       return;                // 结束当前递归
  12.     }
  14.     t.push(nums[cur]);  // 选择当前数
  15.     dfs(cur + 1, nums); // 基于选择的这个数，继续往下递归，考察下一个数
  17.     t.pop(t.length - 1); // 撤销选择当前数
  18.     dfs(cur + 1, nums); // 不选择这个数后，继续往下递归，考察下一个数
  19.   }
  20.   dfs(0, nums);
  21.   return ans;
  22. };

二进制 + 位运算

数组的子集个数为 1 << n ，即 2^n，其中n为数组的元素总数

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number[][]}
  4.  */
  5. var subsets = function (nums) {
  6.   const ans = [];
  7.   const n = nums.length;
  8.   // 数组的子集个数为 1 << n ，即 2^n
  9.   // 遍历所有子集
  10.   for (let mask = 0; mask < (1 << n); ++mask) {
  11.     const t = []; // 存放元素的子集，子集个数总共为 1 << n ，即 2^n
  12.     for (let i = 0; i < n; ++i) {
  13.       // 构造数字代表的集合，各元素存储至 t 子集中
  14.       // 1 << i 即为构造nums数组的第 i 个元素
  15.       // 若 mask & (1 << i) 为真，表示当前的 nums[i]不在当前的子集中，则nums[i]放入 t 子集中
  16.       if (mask & (1 << i)) { 
  17.         t.push(nums[i]);
  18.       }
  19.     }
  20.     ans.push(t);
  21.   }
  22.   return ans;
  23. };

参考：https://jmleetcode-cn.com/problems/subsets/solution/shou-hua-tu-jie-zi-ji-hui-su-fa-xiang-jie-wei-yun-/