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]