LeetCode 78，面試常用小技巧，通過二進制獲得所有子集

今天是LeetCode專題第47篇文章，我們一起來看下LeetCode的第78題Subsets（子集）。

這題的官方難度是Medium，點贊3489，反對79，通過率59.9%。從這個數據我們也可以看得出來，這是一道難度不是很大，但是質量很高的題。的確，在這道題的解法當中，你會學到一種新的技巧。

廢話不多說，我們先來看題意。

題意

這題的題意非常簡單，和上一題有的一拼，基本上從標題就能猜到題目的意思。給定一個沒有重複元素的int型數組，要求返回所有的子集，要求子集當中沒有重複項，每一項當中也沒有重複的元素。

樣例

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

照搬上題

剛拿到手可能有點蒙，但是稍微想一下就會發現，這一題和上題非常接近，兩者唯一的不同就是，子集沒有數量的限制，從空集開始，一直到它本身結束，不論多少個元素都可以。而上一題要求的是有數量限制的，也就是說上一題我們求的其實是限定了k個元素的子集。

想明白這點就簡單了，顯然我們可以復用上一題的算法，我們來遍歷這個k，從0到n，就可以獲得所有的子集了。只要你上一題做出來了，那麼這題幾乎沒有任何難度。如果你沒有看過上一題的文章的話，可以通過傳送門回顧一下：

LeetCode 77，組合挑戰，你能想出不用遞歸的解法嗎？

我們直接來看代碼：

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        # 上一題求解k個組合的解法
        def combine(n, k, ret):
            window = list(range(1, k+1)) + [n+1]
            j = 0
            
            while j < k:
                cur = []
                for i in range(k):
                    cur.append(nums[window[i] - 1])
                ret.append(cur[:])
                
                j = 0
                while j < k and window[j+1] == window[j] + 1:
                    window[j] = j + 1
                    j += 1
                window[j] += 1
                
        # 手動添加空集
        ret = [[]]
        n = len(nums)
        # 遍歷k從1到n
        for i in range(1, n+1):
            combine(n, i, ret)
        return ret

二進制組合

照搬上一題的解法固然是可行的，但是這麼做完全沒有必要，也得不到任何收穫。所以我們應該想一下新的解法。

既然這道題讓我們求的是所有的子集，那麼我們可以從子集的特點入手。我們之前學過，一個含有n個元素的子集的數量是。這個很容易想明白，因為n個元素，每個元素都有兩個狀態，選或者不選。並且這n個元素互相獨立，也就是說某個元素選或者不選並不會影響其他的元素，所以我們可以知道一共會有種可能。

我們也可以從組合數入手，我們令所有子集的數量為S，那麼根據上面我們用組合求解的解法，可以得到：

兩者的結果是一樣的，說明這個結論一定是正確的。

不知道大家看到n個元素，每個元素有兩個取值有什麼想法，如果做過的題目數量夠多的話，應該能很快聯想到二進制。因為在二進制當中，每一個二進制位就只有0和1兩種取值。那麼我們就可以用n位的二進制數來表示n個元素集合取捨的狀態。n位二進制數的取值範圍是，所以我們用一重循環去遍歷它，就相當於一重循環遍歷了整個集合所有的狀態。

這種技巧我們也曾經在動態規劃狀態壓縮的文章當中提到過，並且在很多題目當中都會用到。所以建議大家可以了解一下，說不定什麼時候面試就用上了。

根據這個技巧， 我們來實現代碼就非常簡單了。

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ret = []
        n = len(nums)
        # 遍歷所有的狀態
        # 1左移n位相當於2的n次方
        for s in range(1 << n):
            cur = []
            # 通過位運算找到每一位是0還是1
            for i in range(n):
                # 判斷s狀態在2的i次方上，也就是第i位上是0還是1
                if s & (1 << i):
                    cur.append(nums[i])
            ret.append(cur[:])
            
        return ret

從代碼來看明顯比上面的解法短得多，實際上運行的速度也更快，因為我們去掉了所有多餘的操作，我們遍歷的每一個狀態都是正確的，也不用考慮重複元素的問題。

總結

不知道大家看完文章都有一些什麼感悟，可能第一種感悟就是LeetCode應該按照順序刷吧XD。

的確如此，LeetCode出題人出題都是有套路的，往往出了一道題之後，為了提升題目數量（湊提數），都會在之前題目的基礎上做變形，變成一道新題。所以如果你按照順序刷題的話，會很明顯地發現這一點。如果你從這個角度出發去思考的話，不但能理解題目之間的聯繫，還能揣摩出出題人的用意，這也是一件很有趣的事情。

如果喜歡本文，可以的話，請點個關注，給我一點鼓勵，也方便獲取更多文章。

本文使用 mdnice 排版