Combination Sum
異なる正の整数のリスト candidates と正の整数 target が与えられます。候補の各数を好きな回数だけ使って、合計がちょうど target になる候補の組み合わせをすべて見つけてください。[2, 3, 3] と [3, 2, 3] は同じ組み合わせです。
各組み合わせは昇順に並べ、組み合わせ同士は辞書順に並べて返してください。つまり、2つの組み合わせが異なる最初の位置で、値が小さい方を先にします。
関数
- candidatesinteger-array
- 使用できるさまざまな値を、任意の順序で、それぞれ好きなだけ何度でも
- targetinteger
- すべての組み合わせの合計は正確に達しなければなりません
- 戻り値integer-2d-array
- 目標値の合計になるすべての組み合わせを、それぞれ昇順に並べ、辞書順で列挙
制約
1 ≤ candidates.length ≤ 502 ≤ candidates[i] ≤ 5002 ≤ target ≤ 500- すべての
candidatesの値は異なり、特定の順序にはなっていません。 - 少なくとも1つの組み合わせが
targetに達し、多くても150個の組み合わせが達します。
例
- 入力
- candidates = [6, 2, 3]target = 8
- 出力
- [[2, 2, 2, 2], [2, 3, 3], [2, 6]]
- 説明
- 2が4つの場合、2 + 3 + 3 と 2 + 6 はいずれも合計が8になり、2つ目の値の順に並んでいます。2がない場合、残るのは3と6だけで、それらの合計は3の倍数ですが、8はそうではありません。
- 入力
- candidates = [5, 3, 4]target = 11
- 出力
- [[3, 3, 5], [3, 4, 4]]
- 説明
- 3 + 3 + 5 と 3 + 4 + 4 はどちらも 11 になり、
[3, 3, 5]のほうが先に来ます。2番目の値である 3 が 4 より小さいためです。4 と 5 だけを組み合わせても 11 にはなりません。
- 入力
- candidates = [4, 9]target = 9
- 出力
- [[9]]
- 説明
- 9だけが答えです。4の倍数は4、8、12で、4 + 9はすでに13です。
発展問題
各候補は今後、最大1回までしか使用できず、candidatesには同じ値が複数含まれる場合があります。同じ組み合わせが2回現れないようにするには、探索をどのように変更しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
[2, 3, 3]と[3, 2, 3]は同じ組み合わせです。値を昇順に並べて組み合わせを作る場合、それぞれはいくつの方法で作れますか？候補をソートし、値を1つずつ追加して組み合わせを作ります。
nums[i]を追加した後、次の値には再びnums[i]を使うか、それより後の値を使えますが、それより前の値は使えません。backtrack(start, remaining)を記述します。remainingが 0 の場合、現在の値のコピーを保存します。それ以外の場合は、startからループします。値を追加し、同じインデックスとより小さい残りの値で再帰し、その後、値を削除します。remainingより大きい最初の値でループを終了します。
解説
落とし穴は、同じ組み合わせを2回作ってしまうことです。2, 3, 3と3, 2, 3は同じ答えです。それぞれの組み合わせを昇順で作れば、経路は1通りだけになります。また、候補をソートしておけば、次の値が残りより大きくなった時点で分岐を終了できます。
すべての候補について、あらゆる個数を試します
正しいが、最大のテストでは終わらない
考え方
組み合わせは、各候補を何個使うかで完全に表せます。[2, 3, 3] は2を1個、3を2個、6を0個使う組み合わせです。ソート済みの各候補について、target / c から0までの個数をすべて試し、合計がちょうど target になる選択肢を残します。各組み合わせに対応する個数のリストは1つだけなので、同じ組み合わせが2回見つかることはありません。個数の多い順に試すと辞書順になります。2つの答えが初めて異なる位置では、ある値を多く含む方はその値をまだ使っている一方、もう一方はより大きな値を使っています。
[2, 3, 6] と target 8 の場合、答えは3つで、葉の数は 5 × 3 × 2 = 30 です。target / 2 より大きい候補が1つ増えるごとに葉の数は2倍になるため、このような候補が40個あると 2^40、約10^12になります。
アルゴリズム
- 候補を並べ替え、値ごとに1つの個数を保持します。
choose(i, total)では、各個数kをtarget / nums[i]から0まで試し、choose(i + 1, total + k × nums[i])を呼び出します。- すべての値の個数が決まったら、
totalがtargetと等しい場合に組み合わせを保持し、個数から書き出します。 choose(0, 0)を呼び出します。
def combinationSum(candidates, target):
nums = sorted(candidates)
counts = [0] * len(nums)
result = []
def choose(i, total):
if i == len(nums):
if total == target:
combo = []
for value, k in zip(nums, counts):
combo.extend([value] * k)
result.append(combo)
return
# Most copies first, so the combinations come out in lexicographic order.
for k in range(target // nums[i], -1, -1):
counts[i] = k
choose(i + 1, total + k * nums[i])
counts[i] = 0
choose(0, 0)
return result昇順でバックトラックし、枝刈りする
考え方
nums[i]を配置した後、次の値は再びnums[i]か、それより後の値になります。前の値になることはありません。組み合わせの昇順は1通りしかないため、経路も1通りだけで、[3, 2, 3]が作られることはありません。
昇順に並べた[2, 3, 6]と目標値8の場合、2, 2, 2, 2と2, 3, 3、そして2, 6の経路で8に達します。2, 2, 3の経路では1が残り、6を調べずに停止します。また、3, 3では2が残りますが、どの値を使っても合いません。これは、数え上げの葉30個に対して12回の呼び出しです。
各階層でループは小さい値から試すため、答えは辞書順に得られます。値は正で、どの答えも同じ合計に達するため、ある答えが別の答えの接頭辞になることはありません。
アルゴリズム
- 候補をソートします。
backtrack(start, remaining)では、remainingが0の場合、共有のpathのコピーを保存します。- それ以外の場合は、
iをstartから順にループします。nums[i] > remainingの場合は、後続の値はすべてより大きいため、ループを終了します。 nums[i]を追加し、backtrack(i, remaining - nums[i])を呼び出してから、それを削除します。backtrack(0, target)を呼び出し、保存した組み合わせを返します。
def combinationSum(candidates, target):
nums = sorted(candidates)
result = []
path = []
def backtrack(start, remaining):
if remaining == 0:
result.append(path[:])
return
for i in range(start, len(nums)):
if nums[i] > remaining:
break # sorted, so every later value is too big as well
path.append(nums[i])
backtrack(i, remaining - nums[i]) # i, not i + 1: nums[i] may repeat
path.pop()
backtrack(0, target)
return result
落とし穴と境界ケース
- 現在のインデックスからではなく、各レベルですべての候補をループする。すると、
[2, 3, 3]、[3, 2, 3]、[3, 3, 2]が3つの答えとして出てくる。 iではなくi + 1で再帰する。すると、各値は1回しか現れないため、[2, 2, 2, 2]が見つからなくなる。- コピーではなく
pathそのものを保存する。すると、保存された答えはすべて同じリストになる。このリストはバックトラッキングの終了時には空になっている。 - ソートしていない候補に対して
breakを使う。[6, 2, 3]で残りが2の場合、ループは6で停止し、2を試さない。
よくある質問3
Combination Sum の時間計算量はどれくらいですか？
バックトラッキング探索の計算量は指数時間です。候補がn個、目標値がt、最小の候補がmの場合、組み合わせに含まれる値は最大t/m個で、各値につき選択肢は最大n個あります。そのため、計算量はO(n^(t/m))です。追加の空間計算量は、経路と呼び出しスタックに対してO(t/m)であり、これに出力の分が加わります。
Combination Sumでは、なぜi + 1ではなくiを使って再帰するのですか？
iで再帰すると、次の値にも同じ候補を使えるため、同じ値を複数回使えます。i + 1で再帰すると、その候補を飛ばすため、各候補は最大1回しか使えません。
Combination Sum は動的計画法で解けますか？
はい。0からtargetまでの各合計について、その合計に到達する組み合わせを保持し、候補を1つずつ追加することで、各リストが昇順になるようにします。行き止まりを二度探索することはありませんが、すべての合計についてすべての途中の組み合わせを保存するため、はるかに多くのメモリを消費します。出力自体が指数関数的に増える可能性があるため、通常はバックトラッキングを使います。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def combinationSum(candidates, target):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
candidates = [6, 2, 3] target = 8
期待される出力
[[2, 2, 2, 2], [2, 3, 3], [2, 6]]