[LeetCode] 78. Subsets

轉自LeetCode

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

<Solution>

這題和 Combinations 有點類似

但不一樣的地方是，這次沒有指定 subset 的長度，而是要把所有長度都找出來

一樣還是使用 DFS，但再多一層 for 迴圈來歷遍所有可能長度

code 如下
c++

kotlin

這邊還有一個另一種想法

有 n 個數字，那麼 subset 會有 2^n 個，因為每個數字可以要或不要

舉例 :

所以可以用 bit mask 的概念，來找出所有的 subsets

code 如下

還有一個想法，就是每次都把目前的數字，放到之前的 subsets，來形成新的 subsets

例如 nums = [1,2,3]，目前的 subsets 有 []、[1]、[2]、[1,2]，然後現在要處理 3

就是把 3 依序放入之前的 subsets : [3]、[1,3]、[2,3]、[1,2,3]

這樣全部的 subsets 就是 []、[1]、[2]、[1,2]、[3]、[1,3]、[2,3]、[1,2,3]

code 如下

C++

Java