Day 11 : 子集 Subsets

今天要来解一题以前数学课本第０章都会遇到也很常被我们跳跃式略过的东西。

在看这题之前我们先来了解一个名词 Power sets：
假设有一个集合 X ，我们将 X 中所有的子集合所形成的集合 ，称它为幂集合(Power Set)

举例 Power set的例子：
考虑集合 A={1,2,3}
则其 power set 为 Ｐ(A)={∅,{1},{2},{3},{1,2},{2,3},{1,3},{1,2,3}}
（集合内不需考虑顺序，空集合是所有集合的子集。）

也就是LeetCode中给的例子

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

在这里先自己承认，看到这题题目时候就是看得懂，但实作上有点不知道要从哪个地方切入才对。今天就直接分享两种方式，一种是迭代（iterative）的方式，另一种则是递回的方式。

迭代（iterative）的方式

就以nums = [1, 2, 3]来讲解
我们要的结果是包在一个阵列中 subsets=[ ]

一开始，因为我们知道空集合是所有集合的子集，因此我们可以在一开始就先塞入一个空阵列，也就是在subsets加入一个[] → subsets=[ [ ] ]

然後我们跑到nums[0] = 1的位置上

我们抓出subsets的第一个元素，也就是subsets[0] = [ ]，然後把nums[0] = 1，加入到subsets[0]＝[ ]，产生了[1]新的子集，并把他加到我们的subsets = [ [ ], [ 1 ]]

接着来到了nums[ 1 ] = 2

我们再继续 一样取出 subsets的元素，来分别加入2後，加入到subsets中，subsets = [ [ ], [ 1 ], [ 2 ], [ 1, 2]]

重复以上的方式来得到最後的结果 →[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

过程中，我们每次都要去迭代subsets，且subsets会随着我们拜访nums的长度而增长，可以发现是 2^0 → 2^1 → 2^2 ...，每次都是前一次的两倍

时间复杂度方面，我们知道的subsets个数会是2^n（n为nums的长度），我们每次的操作会是在既有的subset加入新的元素，且所有的子集中最长的长度会是n，最短的长度会是0，取平均来看时间会在O(2^n * n)。同样的空间也是Ｏ(2^n * n)。

接着当然就是直接来写程序码了

var subsets = function (nums) {
  const subsets = [[]];
  for (const element of nums) {
    const length = subsets.length;
    for (let i = 0; i < length; i++) {
      const currentSubset = subsets[i];
      subsets.push(currentSubset.concat(element));
    }
  }
  return subsets;
};

递回的方式

这里主要用的一个观念

例如 P([1, 2]) ⊂ P([1, 2, 3])
也就是P([1, 2, ...., x -1]) ⊂ P([1, 2, 3, x-1, x])

做法上很像是我们做完P([1, 2, ...., x -1])再加上一个([x])
不过自己会觉得这个方法如果没有真的看过，比迭代的方法更不直觉一些，提供大家参考。

var subsets = function powerset(nums, index = null) {
  //一开始呼叫这个函式时我们不传入任何的index，default为null
  // 假设nums = [1, 2, 3]
  if (index === null) {
    //如果index为null，把index摆在阵列的尾巴
    index = nums.length - 1;
  }
  if (index < 0) {
    // 当然如果阵列长度为0，扣掉1後一定小於1，这是基本的状况
    return [[]];
  }
  //element = 3
  const element = nums[index];
  // 递回呼叫powerset
  // powerset(nums, 1)-> P([1, 2])
  const subsets = powerset(nums, index - 1);
  const length = subsets.length;
  for (let i = 0; i < length; i++) {
    // 仿照迭代的方式
    const currentSubset = subsets[i];
    subsets.push(currentSubset.concat(element));
  }
  return subsets;
}

明日题目预告： Merge Intervals