NeetCode 150 [Backtracking]medium:SubsetsⅡ

NeetCodeのSolutionを書いていく

SubsetsⅡ

問題

重複を含む正数の配列numsが渡されます。全てのあり得る
サブセットを返しなさい。

例

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

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

制約

• 1 <= nums.length <= 11
• -20 <= nums[i] <= 20
• 計算量：O(n*(2^n))
• メモリ：O(n)

メモ

入力のnumsの長さが1の状態から考える。
そこから再帰で徐々に配列を増やしながら解決していく。
ただ、前回同様、再帰だとメモリがO(n)では解けない感じがする。
とりあえず一旦再帰で解いてみる。

from collections import Counter
from typing import List


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

            results = backtracking(nums[:-1], results)

            results_counter = [Counter(result) for result in results]
            for result in results.copy():
                new_result = result + [nums[-1]]
                if Counter(new_result) not in results_counter:
                    results.append(new_result)

            return results

        return backtracking(nums, [])