[LeetCode] #78. Subsets

題目

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

直覺解

構想：

用 nums 的長度為遞迴分層

• base case:

  nums 長度 1。只有一個元素的話，所有可能的 subset 就是[有那個元素]、[沒有那個元素]

• inductive case:

  pop nums 的最後一個元素，因此 nums 長度會 -1。用遞迴算出 nums 長度-1 的所有 subset，迭代這些 subset，每一圈都把底下這兩個東西 append 到答案裡：

  1. 這個 subset 有 pop 掉的最後一個元素
  2. 這個 subset 沒有 pop 掉的最後一個元素

python 3 實作：

def subsets(self, nums: List[int]) -> List[List[int]]: 

    if len(nums) == 1: 

        ireturn [[], [nums[0]]] 

         

    result = [] 

    last_item = nums.pop() 

    prev_result = self.subsets(nums) 

    for item in prev_result: 

        icopy = item.copy() 

        iitem.append(last_item) 

        iresult.append(copy) 

        iresult.append(item) 

    return result

效能：

Runtime: 28 ms, faster than 94.45% of Python3 online submissions for Subsets.
Memory Usage: 14.2 MB, less than 92.08% of Python3 online submissions for Subsets.

犯過的錯誤：

• 把上一層的計算結果存到 result 變數：result = self.subsets(nums)，然後在迭代 result 裡的元素時，append 東西到 result 裡，結果變成無窮迴圈

研究別人的解

來源：

成功提交答案後，點選 submission detail 上的長條圖後顯示的答案

別人的 python 3 實作：

class Solution: 

    def subsets(self, nums: List[int]) -> List[List[int]]: 

        nums.sort() 

        path = [] 

        ret = [] 

        dfs(path,ret,nums) 

        return ret 

   

     

def dfs(path,ret,nums): 

    ret.append(path) 

     

    for i in range(len(nums)): 

        dfs(path+[nums[i]],ret,nums[i+1:]) 

    return

效能：

Runtime: 36 ms, faster than 55.92% of Python3 online submissions for Subsets.
Memory Usage: 14.4 MB, less than 48.58% of Python3 online submissions for Subsets.

研究過程：

在回圈裡面放遞迴，好巧妙的手法！不過函式執行的順序看得我眼睛都花了。先記錄一下用 print 輔助研究的程式碼：

class Solution: 

    def __init__(self): 

        pass 

 

    def subsets(self, nums): 

        nums.sort() 

        path = [] 

        ret = [] 

        dfs(path,ret,nums) 

        return ret 

     

def dfs(path,ret,nums): 

    print('<=====') 

    ret.append(path) 

    print('path:', path, 'ret:', ret) 

    for i in range(len(nums)): 

        print('<--------') 

        print('i:', i, 'path+[nums[i]]:', path+[nums[i]]) 

        dfs(path+[nums[i]],ret,nums[i+1:]) 

        print('-------->') 

    print('=====>') 

    return  

   

   

func = Solution() 

nums = [1,2,3] 

print(func.subsets(nums)) 

印出來的結果：

<=====
path: [] ret: [[]]
<-------- // 最外層的 for 迴圈中， i = 0 那一圈
i: 0 path+[nums[i]]: [1]
<=====
path: [1] ret: [[], [1]]
<-------- // 第二層  for 迴圈中， i = 0 那一圈
i: 0 path+[nums[i]]: [1, 2]
<=====
path: [1, 2] ret: [[], [1], [1, 2]]
<--------
i: 0 path+[nums[i]]: [1, 2, 3]
<=====
path: [1, 2, 3] ret: [[], [1], [1, 2], [1, 2, 3]]
=====>
-------->
=====>
-------->
<-------- // 第二層  for 迴圈中， i = 1 那一圈
i: 1 path+[nums[i]]: [1, 3]
<=====
path: [1, 3] ret: [[], [1], [1, 2], [1, 2, 3], [1, 3]]
=====>
-------->
=====>
-------->
<-------- // 最外層的 for 迴圈中， i = 1 那一圈
i: 1 path+[nums[i]]: [2]
<=====
path: [2] ret: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2]]
<--------
i: 0 path+[nums[i]]: [2, 3]
<=====
path: [2, 3] ret: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3]]
=====>
-------->
=====>
-------->
<-------- // 最外層的 for 迴圈中， i = 2 那一圈
i: 2 path+[nums[i]]: [3]
<=====
path: [3] ret: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
=====>
-------->
=====>
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]