解題區►Leetcode►Medium

Leetcode 78 - Subsets

題目

Problem#

給一個 array size = $N$ e.g. [1, 2, 3] 要回傳它的所有可能的子集合(Power set) e.g. [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

想法#

如果用 bit 來表示位置 $i$ 是否有出現，則問題就是數數字 $[0, 2^N]$，每個數字代表一種子集合的狀態

1
2
3
4
5
array = {1, 2, 3}
        ---------
     5 = 1  0  1
       ==========
subset ={1,    3}
  • 時間複雜度: $\mathcal{O}(N\cdot 2^N)$

AC Code#

賞析#