題目連結: 78. Subsets

題目描述:給你一個整數陣列 nums，陣列中的元素互不相同。返回該陣列所有可能的子集（冪集）。
解集不能包含重複的子集。你可以按任何順序返回解集。

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]]

Python

解題思路:
對於 nums 中的每一個數字，我們都有兩個選擇：「要」，還是「不要」。

以下程式碼是使用回溯法來找出所有可能的子集。

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        ans =[]
        def f(index, subset):
            ans.append(subset[:])
            for i in range(index, n):
                subset.append(nums[i])
                f(i+1,subset)
                subset.pop()
        f(0,[])
        return ans

演算法分析:

• 定義一個函式f，這個函式負責從一個給定的起始點 (index)，在一條已有的路徑 (subset) 基礎上，繼續向下探索所有可能性。
• 在函式的每一層，我們都用一個 for 迴圈來遍歷所有當前可選數字。index 確保我們只會向後選擇，避免產生如 [2, 1] 這樣重複的組合。
• f(i + 1, subset)基於這個選擇，向下進行探索。將當前數字加入到 subset 路徑中、當前的選擇為基礎，遞迴呼叫函式自身，當深層的探索結束並返回後，將剛剛加入的數字從 subset 中移除(subset.pop())。
• 使用subset[:]是可以把當前狀態當作副本存放結果裡，這樣就不用額外建立一個陣列來存放，也不會影響到ans的內容。

複雜度分析:

• 時間複雜度為 O(n * 2ⁿ)。

  1. 一個包含 n 個不同元素的集合，其子集的總數為 2ⁿ。
  2. 回溯法會產生所有這 2ⁿ 個子集。
  3. 對於每個子集，我們都需要將其複製一份 (subset[:]) 並存入結果列表中。複製的成本與子集的長度 k 成正比，平均長度為 n/2。

• 空間複雜度： O(n) (這裡的空間複雜度指的是額外的輔助空間，不包括儲存最終答案所需的空間。)。

有問題可以底下留言!
下回見!!