NeetCodeのSolutionを書いていく #
Combination Sum #
https://neetcode.io/problems/combination-target-sum
neetcode.io
問題 #
ユニークな正数の配列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