雲栖号資訊：【 點選檢視更多行業資訊】
在這裡您可以找到不同行業的第一手的上雲資訊，還在等什麼，快來！
這題的官方難度是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，就可以獲得所有的子集了。隻要你上一題做出來了，那麼這題幾乎沒有任何難度。
我們直接來看代碼：
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出題人出題都是有套路的，往往出了一道題之後，為了提升題目數量（湊提數），都會在之前題目的基礎上做變形，變成一道新題。是以如果你按照順序刷題的話，會很明顯地發現這一點。如果你從這個角度出發去思考的話，不但能了解題目之間的聯系，還能揣摩出出題人的用意，這也是一件很有趣的事情。
【雲栖号線上課堂】每天都有産品技術專家分享！
課程位址：
https://yqh.aliyun.com/live立即加入社群，與專家面對面，及時了解課程最新動态！
【雲栖号線上課堂 社群】
https://c.tb.cn/F3.Z8gvnK
原文釋出時間：2020-06-17
本文作者：承志
本文來自：“
掘金”，了解相關資訊可以關注“掘金”