LeetCode78面試常用小技巧?今天是LeetCode專題第47篇文章，我們一起來看下LeetCode的第78題Subsets（子集），我來為大家科普一下關于LeetCode78面試常用小技巧?下面希望有你要的答案，我們一起來看看吧!

LeetCode78面試常用小技巧

今天是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個元素的子集的數量是2^n。這個很容易想明白，因為n個元素，每個元素都有兩個狀态，選或者不選。并且這n個元素互相獨立，也就是說某個元素選或者不選并不會影響其他的元素，所以我們可以知道一共會有2^n種可能。

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

S = C_n^0 C_n^1 ... C_n^n = 2^n

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

不知道大家看到n個元素，每個元素有兩個取值有什麼想法，如果做過的題目數量夠多的話，應該能很快聯想到二進制。因為在二進制當中，每一個二進制位就隻有0和1兩種取值。那麼我們就可以用n位的二進制數來表示n個元素集合取舍的狀态。n位二進制數的取值範圍是[0, 2^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出題人出題都是有套路的，往往出了一道題之後，為了提升題目數量（湊提數），都會在之前題目的基礎上做變形，變成一道新題。所以如果你按照順序刷題的話，會很明顯地發現這一點。如果你從這個角度出發去思考的話，不但能理解題目之間的聯系，還能揣摩出出題人的用意，這也是一件很有趣的事情。

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

本文始發于公衆号：TechFlow