一魚多吃 多角度切入 Subset 子集合生成 Leetcode #78

Ankush Minda on Unsplash

子集合生成是一道很經典的組合類上機考、面試題的題目。

今天，我們會試著用多個不同解度，並且複習以前學過的演算法框架來解這道題目。

原文的題目敘述

目標

給定n個相異的元素，產生所有的子集合。

測試範例

Example 1:

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

Example 2:

Input: nums = [0]
Output: [[],[0]]

演算法1 直覺法 我手寫我口 + DFS

最直接的想法就是，單獨看每個元素，其實只有兩種選擇。

一個是選進來當作子集合的成員，

另一個就是直接跳過不選。

因此，我們只要從第一個元素開始訪問，每層都展開 選擇/不選的兩個分支，
一直到最後一個元素為止。

全部的元素都展開完之後，我們得到的所有可能情況就對應到所有的子集合。

示意圖1

程式碼1 直覺法 我手寫我口 + DFS

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        
        all_subset = []
        bag = []
        
        # ----------------------------------------
        def picker( i:int):
            
            ## Base case aka stop condition
            # Terminate when all items are taken into consideration
            
            if i == len(nums):
                all_subset.append( bag[::] )
                return
            
            
            ## General cases:
            
            # Option_1: pick current item on index i
            bag.append( nums[i] )
            picker( i+1 )
            bag.pop()
            
            # Option_2: not to pick current item on index i
            picker( i+1 )
            
            return 
        # -----------------------------------------
        
        # Let's start item picking from index 0
        picker( 0 )
        return all_subset

演算法2 回溯法+ DFS

前面的演算法框架教學已經提過，這種枚舉類的情境很適合使用回溯法，
考慮每個選擇，做出每個選擇，同樣的模式遞迴展開下一層，撤回選擇。

展開所有分支得到的答案就對應到每個子集合。

教學影片2

示意圖2

程式碼2 回溯法+ DFS

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        
        
        all_subset = []
        bag = []
        
        
        def makeSubsetFrom( startIndex ):
            
            # Add current subset into final result
            # Note: python object is passing by reference, so we have to make a copy
            all_subset.append( bag[::] )
            
            
            ## Base cases aka stop condition:
            # No more element
            if startIndex == len(nums):
                return
            
            ## General cases
            # Current level, we choouse element on index i
            for i in range(startIndex, len(nums) ):
                
                bag.append( nums[i] )           # put this element into bag
                makeSubsetFrom( i+1 )           # make subset from remaining elements
                bag.pop()                       # undo selection
            
            return
        
        #----------------------------------------
        makeSubsetFrom( startIndex = 0 )
        
        return all_subset

演算法3 DP動態規劃

來自於一個基本觀察，每一層的子集合都是前一層的子集合衍伸而來的

情況a:前一層的子集合，照抄，保持不變，相當於當下這個新元素不選。

情況b:前一層的子集合在尾巴串上自己，相當於當下這個新元素選進來。

教學影片3

示意圖3

程式碼3 DP動態規劃 + Top-down 寫法

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        
        # Length = 0 <=> No element, which means empty set
        dp = { 0: [ [] ] }

        def makeFrom( i ):
            
            # look-up DP table
            if i in dp:
                return dp[ i ]

            # General cases:
            # Current subsets
            # = Previous subsets + (Previous subsets padding current element on the tail)
            prev = makeFrom( i-1 )
            cur = prev + [ prevSubset + [ nums[i-1] ] for prevSubset in prev]
            
            dp[ i ] = cur
            return cur

        # ---------------------------------
        return makeFrom( len(nums) )

程式碼3 DP動態規劃 + 等價Bottom-up 寫法

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        
        prev = [ [] ]
        cur = [ [] ]

        for number in nums:

            cur = []
            
            for subset in prev:
                cur.append( subset )
                cur.append( subset + [number] )
            
            prev = cur
        
        return cur

複雜度分析

時間複雜度: O(n * 2^n )

總共有2^n個子集合，每個子集合平均長度為O(n)，
時間耗費在遞迴呼叫和複製子集合上。

空間複雜度: O(n * 2^n )

總共有2^n個子集合，每個子集合平均長度為O(n)，
空間耗費在遞迴深度和複製子集合上。

關鍵知識點

萬變不離其宗，可以發現，總結歸納不管是DP還是DFS+回溯法都是同樣的思考核心。

每次有哪些選擇?

對於子集合來說，每個元素只有兩種可能，就是選 或 不選，
依照題意進行模擬生成子集合即可。

Reference

[1] Leetcode_Subsets