NeetCode 150 [Backtracking]medium:Subsets

NeetCodeのSolutionを書いていく

Subsets

問題

ユニークな正数の配列numsが与えられます。
全てのnumsのサブセットを返しなさい。
重複するサブセットがあってはいけません。サブセットの順序は任意です。

例

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Input: nums = [7]
Output: [[],[7]]

制約

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• 計算量：O(n * (2^n))
• 計算時間：O(n)

メモ

全ての数を選択するかしないかなので、O(2^n)の組み合わせがある。
この組み合わせのサブセットを以下に効率的に作るか。
Setにサブセットを保持し、numsの値を頭から見て追記するかしないかの判断をしながらSetを拡張していくのではだめか？

行けちゃったけど、チョット強引かな。
特にsubsets.copy()のあたりが怪しい。
メモリがO(n)ではなさそう。

from typing import List, Tuple


class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        subsets: set[Tuple] = set()
        subsets.add(())

        for num in nums:
            for subset in subsets.copy():
                subsets.add(subset + (num,))

        return [list(subset) for subset in subsets]