NeetCode 150 [Backtracking]medium:Combination Sum2

NeetCodeのSolutionを書いていく

Combination Sum2

問題

正数の配列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