78. Subsets

Question: Subsets

Solution1

想法：

1. list 中的每一個 element 都有兩種選擇，放或不放

   

   所以 n 個 element 就會有 2^n 的組合

   

2. 由樹狀圖可以知道，每次都選擇「要不要加入新的 element」

   
   1. 加入新的 element，當前的 list append(num)
   2. 回覆原狀，加入新 element 的 list pop()

   再繼續往下走，換下一個 element → Backtracking → DFS

3. 當所有的 element 都遍歷後(search 的長度 == list 的長度時)，就可以 return

4. 遞迴 dfs(i) i 記錄了目前走到 list 的哪一個 index

1. 終止條件：
   

   if i > len(nums) - 1:

   # 將目前的結果 append 到 res 中

   res.append(ls.copy())

   這邊用 shallow copy 就可以，是因為 ls 中都是 immutable 的 element

2. 遞迴條件：
   

   ls.append(nums[i])

   dfs(i + 1)

   
   

   ls.pop()

   dfs(i + 1)

class Solution:

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

# [1, 2, 3]

res = list()

subset = list()

def dfs(i):

if i > len(nums) - 1:

res.append(subset.copy())

return

subset.append(nums[i])

dfs(i + 1)

subset.pop()

dfs(i + 1)

dfs(0)

return res

遞迴邏輯

這裡簡單畫一下整個 recursion function run 的過程

感想：如果我會做動畫就好惹～

Solution2 for loop + DFS

因為不重複

• 如果第一個數選 1 ，第二個數只能選 2 或 3
• 如果第一個數選 2，第二個數只能選 3
• 如果第一個數選 3，後面沒有人可以選

每次進入遞迴 index + 1， for loop i 到最後一個數

在進入遞回前，把組合加入 res 中

class Solution:

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

res = list()

subset = list()

def dfs(i):

res.append(subset.copy())

if i > len(nums) - 1:

return

for i in range(i, len(nums)):

subset.append(nums[i])

dfs(i + 1)

subset.pop()

dfs(0)

return res

reference: 這一篇不錯，提供兩種解法，其中一種是，我想寫的 for loop ，但不知道怎麼與 DFS 結合，但是他辦到了！！

Video Solution