題目出處

難度

Medium

個人範例程式碼

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        if not nums:
            return [[]]

        ans = []
        self.dfs(nums, 0, [], ans)

        # print(ans)        
        return ans

        # [] 
        # [1] [12] [123]
        #     [13]
        # [2] [23]
        # [3]

    def dfs(self, nums, start, combination, ans):

        ans.append(combination[:]) # deepcopy

        # end of recursion        
        # define and split (use or not use)
        for i in range(start, len(nums)):       
            combination.append(nums[i])
            self.dfs(nums, i+1, combination, ans)
            combination.pop() # backtracking

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

算法說明

經典 DFS 的組合問題，思考方式如下：

每一層我們都可以決定「取特定數字或不取」，但取或不取，順序都要一直往後。

input handling

如果沒有 nums，return [[]]

Boundary conditions

用 dfs 內的 for loop 控制搜尋範圍

Reference

子集 · Subsets