Subset Sum Problem
numsには正の整数が格納されており、targetは正の整数です。各位置から最大1回まで値を選んで、合計をちょうどtargetにできますか？できる場合はtrueを、どの選び方でもできない場合はfalseを返してください。
関数
- numsinteger-array
- 選択できる正の値
- targetinteger
- 選んだ値の合計がちょうど達しなければならない値
- 戻り値boolean
- 値の合計がちょうど target になる場合は true、そうでない場合は false
制約
1 ≤ nums.length ≤ 2001 ≤ nums[i] ≤ 1041 ≤ target ≤ 104
例
- 入力
- nums = [8, 3, 11, 5, 7]target = 15
- 出力
- true
- 説明
- 8 + 7 = 15 なので、答えは
trueです。3 + 5 + 7 を選んでもうまくいきます。1つ選べば十分です。
- 入力
- nums = [6, 9, 12, 15]target = 20
- 出力
- false
- 説明
- すべての値は3の倍数なので、それらの合計もすべて3の倍数です。20は3の倍数ではないため、答えは
falseです。
- 入力
- nums = [4, 1, 2]target = 8
- 出力
- false
- 説明
- 3つの値をすべて合わせると 4 + 1 + 2 = 7 となり、8より小さいため、どの選び方でも8に達することはできず、答えは
falseです。
発展問題
異なる位置にある同じ値は、別々の選択として数えます。targetに到達する選択はいくつありますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
nums[0]から始めます。それを選ぶ場合、残りの値でtarget-nums[0]を作る必要があります。選ばない場合は、残りの値でtargetを作る必要があります。どちらも、より短い配列で同じ問いを解くことになります。位置
i以降の値で合計rを作れるかどうかは、iとrだけに依存し、rがtargetを超えることはありません。そのため、異なる問題は最大でも約 200 × 10^4 個で、それぞれ一度だけ答えればよいです。0 から
targetまでの各合計値に1つずつブール値を用意し、最初は合計値0だけを到達可能にします。値を1つずつ追加します。合計値sは、s-numがすでに到達可能であれば到達可能になります。値を2回使わないよう、合計値を大きい方から小さい方へ更新し、targetの値を答えとして読み取ります。
解説
各値について選ぶか選ばないかの2通りがあるため、200個の値では2^200通りの選び方があります。ただし、重要なのは target ≤ 10^4 までの合計だけです。ここまでの値で作れる合計を記録します。新しい値が加わるたびに、その値の大きさだけ記録をずらせば、探索は n × target 個の真偽値からなる表になります。
各値を取得するかスキップする
正しいが、最大のテストでは終わらない
考え方
canMake(i, remaining)は、位置i以降の値を使って、ちょうどremainingを作れるかどうかを尋ねます。収まる場合はnums[i]を選び、残りの値でremaining-nums[i]を作ります。それが失敗したら、nums[i]をスキップします。選ぶたびに1つの経路になるため、解が存在すれば探索によってその選び方が見つかります。
解が存在しない場合は、すべての選び方をたどります。3の倍数が200個あり、それぞれ最大300で、目標値が9998の場合、どの選び方も目標値には届きません。しかし、どの33個を選んでも目標値を下回ります。経路は10^37を超えます。
アルゴリズム
canMake(i, remaining)を記述します。remainingが0なら、選択は完了です。trueを返します。残りの値がなく、まだ作る必要がある場合はfalseを返します。nums[i] ≤ remainingかつcanMake(i+1, remaining-nums[i])がtrueなら、trueを返します。- それ以外の場合は
canMake(i+1, remaining)を返します。 canMake(0, target)を返します。
def isSubsetSum(nums, target):
n = len(nums)
# Can some of nums[i], nums[i+1], ... add up to exactly remaining?
def can_make(i, remaining):
if remaining == 0:
return True
if i == n:
return False
if nums[i] <= remaining and can_make(i + 1, remaining - nums[i]):
return True # take nums[i]
return can_make(i + 1, remaining) # skip it
return can_make(0, target)到達可能な合計値の表を埋める
考え方
再帰処理では、位置と残りの合計が target の間の値だけが状態となり、同じ組にたどり着く経路が多数あります。代わりに表を埋めましょう。made[i][s] は、最初の i 個の値から選んだ数の合計がちょうど s になる場合に true です。何も選ばない場合、合計は 0 になります。num = nums[i-1] とすると、合計 s が作れるのは、num を使わずに作れていた場合、つまり made[i-1][s] が true の場合か、s ≥ num のときに num を加えて s-num を完成できる場合、つまり made[i-1][s-num] が true の場合です。
最初の例では、8 を処理した後に作れる合計は 0 と 8 です。3 を加えると 3 と 11 が作れ、11 を加えると 14 だけが作れます。5 を加えると 5 と 13 が作れ、8 + 7 で 15 になります。制約の上限では、表のセル数は 201 × 10001 で、処理ステップ数は約 2 × 10^6 です。
アルゴリズム
madeを(n+1)行、(target+1)個のブール値で確保し、すべてfalseにします。空の選択を表すため、made[0][0]をtrueにします。- 行
iは、i= 1からnまで、値num = nums[i-1]を扱います。 - 0から
targetまでの各合計sについて、made[i][s]をmade[i-1][s]に設定します。 s ≥ numであり、made[i-1][s-num]がtrueの場合、made[i][s]をtrueに設定します。made[n][target]を返します。
def isSubsetSum(nums, target):
n = len(nums)
# made[i][s]: some of the first i values add up to exactly s
made = [[False] * (target + 1) for _ in range(n + 1)]
made[0][0] = True
for i in range(1, n + 1):
num = nums[i - 1]
for s in range(target + 1):
# leave num out, or put it in on top of a sum of s-num
made[i][s] = made[i - 1][s] or (s >= num and made[i - 1][s - num])
return made[n][target]上から更新される、和の1行
考え方
各行はその直前の行だけを参照するため、1つの配列 made[s] で保持できます。上向きに上書きすると値が自分自身を参照するようになります。nums = [5]、target が 10 の場合、s = 5 が true になり、次に s = 10 がその新しいエントリを参照するため、5を2回使うことになります。
代わりに、target から num まで降順に進めます。s-num の読み取り先は、走査中にまだ書き換えていない下のセルなので、num を処理する前の行を参照します。作れた合計は作れたままなので、made[target] が true になった時点ですぐに終了できます。メモリ使用量は target + 1 個の真偽値に減ります。
アルゴリズム
target + 1個の真偽値を持つ配列を1つ用意し、made[0]だけを true にします。- 値を順番に取り出します。各
numについて、sをtargetからnumまで降順に処理します。 made[s-num]が true なら、made[s]に印を付けます。made[target]に印が付いたら、すぐにtrueで終了します。- すべての値を使い切っても先に終了しなかった場合、答えは
falseです。
def isSubsetSum(nums, target):
# made[s]: some of the values seen so far add up to exactly s
made = [False] * (target + 1)
made[0] = True
for num in nums:
# Downward, so made[s - num] still ignores num
for s in range(target, num - 1, -1):
if made[s - num]:
made[s] = True
if made[target]:
return True
return False
落とし穴と境界ケース
- 合計値を増やす方向にループすると、同じ値を2回使ってしまいます。
[3]で目標値が9の場合、trueと判定されます。 made[0] = trueを忘れること。すべての合計値は空の選択から始まるため、答えはすべてfalseになります。- 最大の値から先に選ぶこと。目標値が10で
[6, 5, 5]の場合、6を取ると残りは4になり、どの値を使っても作れませんが、5 + 5 = 10です。 targetを超える値は、[10000]で目標値が1の場合のように、何も変えてはいけません。Swiftのnum...targetはプログラムを停止させ、Rの(num+1):(target+1)は逆向きに数えるため、まずnum ≤ targetを確認してください。- LuaとRでは、合計値
sの項目はインデックスs + 1にあります。
よくある質問4
部分和問題の時間計算量はどのくらいですか？
このテーブルの計算量は O(n × target) 時間で、値が200個、targetが10^4の場合、約2 × 10^6ステップです。また、行を1つにすることでメモリを O(target) に抑えられます。計算量はtargetの数値の大きさに左右されるため、この方法は擬多項式時間であり、targetが10^18のような場合には役に立ちません。一般に、部分和問題はNP完全です。
部分和問題は、等分割部分集合問題や0/1ナップサック問題とどのように関連していますか？
Partition Equal Subset Sum は、合計が偶数であることを確認したうえで、target = total / 2 とする Subset Sum です。Subset Sum は、各値をその重さとして扱い、ナップサックをちょうど満たす 0/1 ナップサック問題なので、テーブルには最適値ではなく真偽値が格納されます。
部分和問題は負の数でも機能しますか？
考え方は合っていますが、上記のコードは動作しません。負の数がある場合、到達可能な合計値は負の数の合計から正の数の合計までの範囲になるため、すべてのインデックスをその最小の合計値だけずらし、同じ方法で行を埋めます。残りの合計より大きい値は、もうスキップできません。
目標を達成する値をどのように見つけますか？
テーブル全体を保持し、made[n][target]から始めます。1行ずつ上に進みます。made[i-1][s]がtrueなら、nums[i-1]は必要ありませんでした。そうでなければ、それを記録してsから差し引きます。有効な要素を1つ選んだ状態で合計が0になると終了です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def isSubsetSum(nums, target):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
nums = [8, 3, 11, 5, 7] target = 15
期待される出力
true