[Leetcode解題] Subsets - dfs解

11 February 2022
medium recusion dfs

題目

78. Subsets 這是一道關於「子集」的題目。給定一個整數數組 nums，其中所有元素均為唯一的，請返回所有可能的「子集」（即集合的幂集）。 解決方案集不得包含重複的子集。您可以以任意順序返回解決方案。

解題思路

這個題目需要我們返回一個數組的所有子集。我們可以使用深度優先搜索來解決這個問題。

我們定義一個名為dfs的函數，它接受兩個參數：$start$和$path$。$start$是搜索的起點，$path$是當前搜索的路徑。

首先，我們將當前路徑添加到結果列表中，然後遍歷整個數組，從當前起點開始。對於每個數字，我們呼叫dfs函數，傳遞$i + 1$作為下一個起點和$path + [nums [i]]$作為新的路徑。

最後，我們以[]作為起始路徑自訂dfs（0，[]），並返回結果列表。

實作

以下是一個使用回溯法的 Python 解決方案：

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []
        n = len(nums)
        
        def dfs(start, path):
            result.append(path)
            for i in range(start, n):
                dfs(i + 1, path + [nums[i]])
        
        dfs(0, [])
        return result

複雜度

本題的時間複雜度是 $O(2^n * n)$，其中 $n$ 是 $nums$ 數組的長度。

實際上，因為每個元素只需要添加到結果集一次，所以實際的時間複雜度比理論時間複雜度略低，大約為 $O(2^n * n)$。