今天要來解一題以前數學課本第０章都會遇到也很常被我們跳躍式略過的東西。

在看這題之前我們先來了解一個名詞 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