Combination Sum
異なる正の整数のリスト candidates と正の整数 target が与えられます。値の合計がちょうど target になる候補の組み合わせをすべて見つけてください。各候補は好きなだけ使用できます。同じ値を同じ回数使用する組み合わせは同一とみなされるため、[2, 3, 3] と [3, 2, 3] は1つとして数えます。
各組み合わせの値を昇順に並べて返し、組み合わせ自体は辞書順に並べてください。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つ合わせると8になり、2 + 3 + 3や2 + 6でも8になります。3つとも2から始まるので、2つ目の値で順序が決まります。つまり、2、次に3、そして6です。2がなければ、3と6だけになり、それらをどのように組み合わせても3の倍数になりますが、8は3の倍数ではありません。
- 入力
- candidates = [5, 3, 4]target = 11
- 出力
- [[3, 3, 5], [3, 4, 4]]
- 説明
- 3 + 3 + 5 と 3 + 4 + 4 はどちらも 11 になります。最初の値は同じで、2番目の値では 3 のほうが 4 より小さいため、
[3, 3, 5]が先になります。4 と 5 だけを組み合わせても 11 にはなりません。
- 入力
- candidates = [4, 9]target = 9
- 出力
- [[9]]
- 説明
- 9単独でも組み合わせです。4は9を通り過ぎる途中で4、8、12だけを作り、4 + 9はすでに13なので、
[9]だけが答えです。
提出時に隠しテスト+12件
発展問題
各候補は最大1回までしか使えなくなり、candidatesには重複した値が含まれる場合があります。同じ組み合わせが2回現れないようにするには、探索をどのように変更すればよいでしょうか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
[2, 3, 3]と[3, 2, 3]は同じ組み合わせです。値を昇順に並べて組み合わせを作る場合、それぞれの組み合わせは何通りの方法で作れますか？候補を並べ替え、値を1つずつ追加して組み合わせを作ります。
nums[i]を追加した後、次の値には再びnums[i]を使うか、それより後の値を使えますが、それより前の値は使えません。backtrack(start, remaining)を記述します。remainingが0の場合は、現在の値のコピーを保存します。それ以外の場合は、startからループします。値を追加し、同じインデックスとより小さい残りの値で再帰呼び出しを行い、その後値を削除します。remainingより大きい最初の値でループを終了します。
解説
各回答は候補の多重集合です。落とし穴は、同じ多重集合を複数回作ってしまうことです。2、次に3、次に3を選ぶ場合と、3、次に2、次に3を選ぶ場合は、同じ組み合わせになります。この問題を解決する考え方は、各組み合わせを昇順で作ることです。そうすれば作り方は必ず1通りになり、さらに候補をソートしておけば、次の値が残りの値を超えた時点で分岐を止められます。同じ昇順の探索によって、最後にソートしなくても組み合わせを辞書順で得られます。
すべての候補について、すべての個数を試します
正しいが、最大のテストでは終わらない
考え方
組み合わせは、各候補を何個ずつ使うかで完全に表せます。[6, 2, 3] と target 8 の場合、答えの [2, 3, 3] は 2 が1個、3が2個で、6は使いません。したがって、すべての答えを見つける方法の一つは、各候補について考えられる個数をすべて試し、合計がちょうど target になる選択肢を残すことです。候補 c は最大でも target / c 回使えるので、その個数は0からその上限までです。
候補をソートしたあと、候補ごとに1段ずつある決定木をイメージしてください。レベル i では、i番目の値を何個取るかを決め、最下部の各葉が個数の完全な選択肢を1つ表します。各多重集合は個数のリストが一つだけなので、同じ組み合わせが二度見つかることはありません。最大個数から試すと、必要な順序にもなります。2つの答えで、ある値の個数が初めて異なるとき、より多くの個数を含む方は、もう一方がすでにより大きな値を含んでいるところに、その小さな値をまだ含んでいるため、先に来ます。
問題は木の大きさです。葉の数は、すべての候補について target / c + 1 を掛け合わせた値です。ソート済みの [2, 3, 6] と target 8 の場合、答えは3つなのに葉は5 × 3 × 2 = 30個になります。target / 2 より大きい候補は、最大でも一度しか使えないにもかかわらず葉の数を2倍にするため、そのような候補が40個あるだけで、葉の数は2^40、つまり約10^12個になります。大きなテストはこのように作られているため、この方法では最後まで処理できません。
アルゴリズム
- 候補を並べ替え、値ごとに1つずつ個数を格納する配列を作ります。
- 値のインデックス
iの個数を決めるchoose(i, total)を記述します。 kをtarget / nums[i]から 0 まで減らしながら、個数をkに設定し、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昇順でバックトラックし、枝刈りする
考え方
それぞれの組み合わせを、書き留めるときと同じように、値を1つずつ昇順で組み立てます。開始インデックスによって、この順序が保たれます。nums[i]を置いた後、候補の値は繰り返し使えるため、次の値に再びnums[i]を使うことも、それより後の値を使うこともできますが、それより前の値を使うことはできません。そのため、インデックスiを置いた呼び出しでは、i以降だけをループします。それぞれの組み合わせには昇順の並び方がちょうど1つだけあるので、木の中の経路も1つだけです。そのため、[3, 2, 3]のような重複は決して作られません。
ソート済みの[2, 3, 6]とtarget 8に対する木全体を見てみましょう。根には8が残っており、2、3、6を試します。2の下では6が残ります。2、2の下では4が残り、2、2、2では2が残ります。そこにもう1つ2を加えると答えの[2, 2, 2, 2]になり、2、2、3では1が残って行き止まりになります。2、3の下では3が残り、3と6だけを試せます。3を選ぶと[2, 3, 3]になります。2、6の下には何も残りません。つまり[2, 6]です。3の下では3と6だけを試せますが、3、3では2が残り、どちらも埋めることはできません。6の下では2が残り、6だけを試せます。呼び出しは全部で12回で、最初の方法の30個の葉と比べて少なくなります。
ソートすると、行き止まりで早めに処理を止められます。nums[i]が残りの値より大きければ、それ以降の値もすべてさらに大きいので、残りを試す代わりにbreakでループを抜けます。上の木で、残りが1の2、2、3のノードでは、3を見て入らないと判断した時点で、6を見ることはありません。探索で訪れるのは、合計がtarget以下のままの接頭部分だけです。そのため、最初の方法では処理が大変になる大きなテストも、ここでは数千回の呼び出しで済みます。
出力順も同じ探索から決まります。各レベルでループは小さい値から試し、それぞれの組み合わせは昇順に並べられます。2つの答えは、経路が分岐するレベルで初めて異なります。そのレベルで小さい値を選ぶ経路が先に探索されるため、答えは辞書順に出力されます。値は正で、どちらの組み合わせも同じ合計に達するため、ある組み合わせが別の組み合わせの接頭部分になることはありません。
アルゴリズム
- 候補を昇順に並べ替えます。
- 1つのリスト
pathを共有するbacktrack(start, remaining)を記述します。remainingが0の場合、pathのコピーを保存します。 - それ以外の場合は、
iをstartから末尾までループします。nums[i] > remainingの場合は、以降の値はすべて大きいため、ループを終了します。 nums[i]を追加し、値を繰り返し使えるようにi + 1ではなく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を使うこと。残りが2で候補が[6, 2, 3]の場合、ループは6で停止し、2を試しません。 - ソートされていない入力の順序どおりに組み合わせを返すこと。期待されるリストは辞書順であり、ソート済みの探索なら追加のソートなしでその順序になります。
- LuaとRでは配列のインデックスは1から始まるため、最初の呼び出しはインデックス1から始まり、ループは配列の長さまで実行されます。
よくある質問4
Combination Sum の時間計算量はどのくらいですか？
バックトラッキング探索の計算量は指数関数的です。候補の数が n、目標値が t、最小の候補が m の場合、1つの組み合わせに含まれる値は最大でも t/m 個であり、各ステップで選べる候補は最大 n 個なので、計算量は O(n^(t/m)) で上から抑えられます。候補をソートして枝刈りすることで、合計が依然として t 以下の接頭部分だけを探索するため、実際の呼び出し回数はこれを大きく下回ります。追加の空間計算量は、現在の経路と呼び出しスタックに対して O(t/m) であり、これに出力分が加わります。
Combination Sumでは、なぜi + 1ではなくiを使って再帰するのですか？
iで再帰すると、次の値に同じ候補を再び使えるようになり、これによって値を複数回使えます。i + 1で再帰するとその候補を通り過ぎるため、各候補を最大1回だけ使うバリエーションになります。このルールのもう一方も同じくらい重要です。iより前のインデックスに戻らないことで、すべての組み合わせが昇順になり、重複も防げます。
セットを使わずに重複する組み合わせを避けるにはどうすればよいですか？
すべての組み合わせを、昇順で固定された順序で生成します。開始インデックスによってこれを保証します。nums[i]を配置した後、探索ではnums[i]以降の値だけを調べます。すると、探索木の中で各組み合わせに至る経路はちょうど1つとなるため、それぞれ1回だけ生成され、集合や最後の重複排除は必要ありません。
Combination Sumは動的計画法で解けますか？
はい。0からtargetまでの各合計について、その合計に達する組み合わせのリストを保持し、候補を1つずつ追加して、各リスト内の値が昇順のままになるようにします。これは、硬貨で金額を作る方法を数えるのと同じ考え方です。行き止まりを二度探索することはありませんが、各合計についてすべての途中段階の組み合わせを保存するため、バックトラッキングよりもはるかに多くのメモリを消費し、最後にリストの並べ替えが必要になる場合もあります。出力自体が指数関数的な大きさになり得るため、通常はバックトラッキングを使います。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def combinationSum(candidates, target):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
candidates = [6, 2, 3] target = 8
期待値
[[2, 2, 2, 2], [2, 3, 3], [2, 6]]