NeetCodeのSolutionを書いていく #
SubsetsⅡ #
https://neetcode.io/problems/subsets-ii
neetcode.io
問題 #
重複を含む正数の配列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, [])