NeetCode 150 [Backtracking]medium:Combination Sum

NeetCodeのSolutionを書いていく

Combination Sum

問題

ユニークな正数の配列numsとターゲットとする正数targetが与えられます。
選択した数の合計がtargetになるユニークなnumsの組み合わせを全て返すことです。

numsに含まれる数であれば何度でも使って構いません。
数の登場回数が同じであればそれは同一とみなし、そうでなければ同一ではありません。
組み合わせ内の数字の順番も、組み合わせ自体の順番も問われません。

例

Input:
nums = [2,5,6,9]
target = 9
Output: [[2,2,5],[9]]

Input:
nums = [3,4,5]
target = 16
Output: [[3,3,3,3,4],[3,3,5,5],[4,4,4,4],[3,4,4,5]]

Input:
nums = [3]
target = 5
Output: []

制約

• All elements of nums are distinct.
• 1 <= nums.length <= 20
• 2 <= nums[i] <= 30
• 2 <= target <= 30
• 計算量：O(2^(t/m)) tはtarget、mはnumsの最小値とします。
• メモリ：O(t/m)

メモ

「Backtracking」という問題の種類なので、再帰で解くはず。
m=numsの最小値が計算量、メモリに影響しているのはヒントになりそう。
最小値を使う？

Outputの個々の配列は高々t/mのサイズになる。
なので、配列サイズが t/mtを超えたら評価を打ち切って良い。
同じように配列合計数がtargetを超えたときも評価を打ち切って良い

Outputはクラスのメンバとして保持しておく。
numsに含まれる数字をtempに積みながら調査をする。
numsとtargetとtempを引数に受け付ける再帰関数を作る。

重複チェックはCounterを使って実施する。
回答と比べるといまいちな実装になった。
もっとしっかり事前に考える必要がありそうだ。

from collections import Counter
from typing import List


class Solution:
    def combinationSum(self, nums: List[int], target: int) -> List[List[int]]:
        output: List[List[int]] = []

        def backtrackingCheck(nums, target, maxLen, temp):
            for n in nums:
                add_value = sum(temp) + n

                # ターゲット数に達した場合はoutputに格納するかチェック
                if add_value == target:
                    tempCopy = temp.copy()
                    tempCopy.append(n)
                    if not output or (Counter(tempCopy) not in [Counter(o) for o in output]):
                        output.append(tempCopy)
                    continue
                else:
                    # あり得る加算数を超えていたら次の再帰処理は行わない
                    if len(temp) + 1 == maxLen:
                        continue
                    # 合計値がターゲットを超えていたら次の再帰処理は行わない
                    if add_value > target:
                        continue

                tempCopy = temp.copy()
                tempCopy.append(n)
                while backtrackingCheck(nums, target, maxLen, tempCopy):
                    pass

        backtrackingCheck(nums, target, target // min(nums), [])
        return output