0078. Subsets (Medium)

(當然，Medium的拍手也可以多拍幾下啦XD)

Question

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

分析/解題

給定一組內含相異的整數的集合nums，試回傳其power set。
(所有可能的子集合，包含空集合)

我們先考慮一下所謂的子集合。
所謂的子集合就是在指說，在nums所有的元素(element)中，
有哪些要被用，哪些不要被用的所有組合。
所以對於每個數都有加進去/不加進去的兩種可能，
如果nums有N個元素，所有的組合的可能是就會是2^N。

我們可以透過上述的思路來建構遞迴的函式。
首先，我們先產生一個subset，
用來存放走到當前的狀況 ，
而一個確定可以放進結果res的subset，
必須是將整個nums走完且決定誰要進，誰不要進才行。
要放進subset和不放都是可行的選擇，
那麼我們就必須要分岔成兩條路 ：

1. 將當前遇到的數字置之不理，直接朝向下一個index走
2. 先將當前遇到的數字加進subset中 ，再朝下一個index走
   留意當回到上一層 的時候，這個index遇到的數字同樣應該要被取消掉 ，
   所以我們應該要從subset中拔掉最後一個數字 。

那麼遞迴的尾端 ，自然就是當index走超過範圍 的時候，
此時我們應該將這個subset作為其中一個結果放入到res中，
並回到上一層。

依此，我們可以寫成如下的程式碼。
在Java的部分，List使用LinkedList或ArrayList皆可，
ArrayList適用於需要取得某個點的値，
而LinkedList在儲存時會稍微快一點，
請留意我們在新增組合時是使用new ArrayList<>(subset) ，
用以加入subset的複本來放入res中。
如果單純放subset的話，由於大家都指向相同的位置，
後面修改subset的時候會導致res內的內容也同部被改到，
請務必留意XD

Java

這邊也提供了參考的其它解，包含了迭代解和另一種遞迴解，
概念都是**拿現在的所有組合和新的數字，決定要加或不要加，
用以衍生出兩倍的組合。**這種方法其實概念上類似我們之前提到的Gray Code的解法，
用原先的部分來組新的東西，有興趣可再參考。

Python的部分一樣需注意subset要使用copy來複製一份使用。

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(2^N)/O(2^N)，因每種組合皆須經過一次，且都要存入結果。)

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~