NeetCodeのSolutionを書いていく #
Combination Sum2 #
https://neetcode.io/problems/combination-target-sum-ii
neetcode.io
問題 #
正数の配列candidatesが与えられます。対象となる正数targetもあるし、重複した値も含んでいます。
合計値がtargetになるcandidatesのユニークな組み合わせをすべて返しなさい。
candidatesの要素は多くても一度しか使えません。回答のsetは重複した組み合わせを含んではいけません。
組み合わせ自体の順番も、組み合わせ内の要素の順番も問われません。
例 #
Input: candidates = [9,2,2,4,6,1,5], target = 8 Output: [ [1,2,5], [2,2,4], [2,6] ]
Input: candidates = [1,2,3,4,5], target = 7 Output: [ [1,2,4], [2,5], [3,4] ]
制約 #
- 1 <= candidates.length <= 100
- 1 <= candidates[i] <= 50
- 1 <= target <= 30
- 計算量：O(n*(2^n)) tはtarget、mは
numsの最小値とします。 - メモリ：O(n)
メモ #
前回と何が違うんだろう。
- 入力配列に重複する要素がある。
- 入力配列の要素は何度も使ってはいけない。使ったら消える
candidatesでループしてcandidate毎に使うか使わないか判定する。 合計値がtargetになったらOutputにappendする。 組み合わせの重複チェックが力技になってしまった。 candidatesをソートしておいて、同じ値の場合は次の枝の候補にしなければいいらしい。 (絶対うまく言えていない・・・)
from collections import Counter
from typing import List
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
max_index = len(candidates) - 1
res: List[List[int]] = []
def backtrack(work: List[int], index):
if index > max_index:
return
#########################
# 新しい要素を使わないパターン
#########################
backtrack(work.copy(), index + 1)
#########################
# 新しい要素を使うパターン
#########################
e = candidates[index]
work.append(e)
# 回答が出た場合は使うバターンの解析は終了
if sum(work) == target:
# パターンの重複をチェック
if Counter(work) not in [Counter(r) for r in res]:
res.append(work.copy())
# 数を超えた場合も次の調査は不要
elif sum(work) > target:
pass
# それ以外だけ調査を続ける
else:
backtrack(work.copy(), index + 1)
backtrack([], 0)
return res