Target Sum
非負整数の配列 nums と整数 target が与えられます。すべての数の前にプラス記号またはマイナス記号を付け、順序を保ったまま式を評価します。式の値が target になる符号の選び方がいくつあるかを返してください。2^n 通りの選び方はそれぞれ個別に数えるため、+0 と -0 は異なる2通りの選び方です。
関数
- numsinteger-array
- それぞれに符号が付く数値
- targetinteger
- 式が等しくなければならない値
- 戻り値integer
- 式の値が target と等しくなる符号の選び方の数
制約
1 ≤ nums.length ≤ 200 ≤ nums[i] ≤ 1000numsの合計は1000以下です。-1000 ≤ target ≤ 1000- 答えは最大でも 220 で、32ビット符号付き整数の範囲内に十分収まります。
例
- 入力
- nums = [2, 1, 1]target = 2
- 出力
- 2
- 説明
+2 +1 -1と+2 -1 +1はどちらも 2 になります。2 にマイナスを付けた場合、到達できる最大値は -2 + 1 + 1 = 0 なので、ほかの選択肢はどれも成り立ちません。
- 入力
- nums = [0, 4, 4]target = 0
- 出力
- 4
- 説明
- 2つの4は反対の符号である必要があります。
+4 -4または-4 +4で、どちらの場合も0にはどちらの符号を付けてもかまいません。したがって、選択肢は2 × 2 = 4通りです。
- 入力
- nums = [6, 3]target = 4
- 出力
- 0
- 説明
- 可能な値は 9、3、-3、-9 の4つです。符号を反転すると合計はその数の2倍だけ変化するため、6 + 3 = 9 のように結果はすべて奇数となり、偶数の目標値である 4 には決して到達しません。
発展問題
合計値を添字とする配列がメモリに収まらない場合でも、最大10^9の値を持つ数値を最大40個扱えますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
各数について両方の符号を試す方法もあります。これは
2^n個の式になります。異なる符号の接頭辞が同じ累計値になることが多く、その後はまったく同じように振る舞うことに注目してください。プラスが付く数の合計を
P、マイナスが付く数の合計をNとします。P - N = targetかつP + N = sum(nums)であることがわかっています。これからPについて何がわかりますか？P = (sum + target) / 2なので、その値の合計になるnumsの部分集合の数を数えます。sに到達する部分集合の数であるways[s]を保持し、各数について、sの大きい方から更新します。sum + targetが奇数の場合、または|target| > sumの場合は、すぐに 0 を返します。
解説
各数には2通りの符号があるため、式は 2^n 個あります。位置と累計値で数えると、同じ累計値に至る符号の接頭辞をまとめられます。さらに、正の符号が付いた数は合計が一定の部分集合を形成するため、問題は指定された合計を持つ部分集合の個数を数えることになり、nums の合計を S とすると、計算時間は O(n × S) です。
すべての数値について、両方の符号を試してください
正しいが、最大のテストでは終わらない
考え方
数値を左から右へ順に見ていき、累計を記録しながら、それぞれの数値で2通りに分岐します。その数値を足すか、引くかです。すべての数値に符号を付けたら、合計がtargetと等しい場合に1を数えます。符号の選び方はそれぞれ1つの経路に対応するので、数を合計すれば答えになります。
選び方ごとに葉が1つあります。数値が20個なら葉は2^20 ≈ 10^6個で、数値が1つ増えるごとに処理量は2倍になります。
アルゴリズム
count(i, total)を記述します。これは、iより前の数の合計がすでにtotalであるとき、nums[i..]に符号を付ける方法の数です。i == nの場合、total == targetなら 1 を返し、そうでなければ 0 を返します。- それ以外の場合は、
count(i+1, total + nums[i]) + count(i+1, total - nums[i])を返します。 - 答えは
count(0, 0)です。
def findTargetSumWays(nums, target):
n = len(nums)
def count(i, total):
# Ways to sign nums[i:] so that the whole expression ends at target
if i == n:
return 1 if total == target else 0
return count(i + 1, total + nums[i]) + count(i + 1, total - nums[i])
return count(0, 0)位置と累計値をメモ化する
考え方
count(i, total) は、合計を生み出した符号ではなく、i と total のみに依存します。nums = [1, 1, 1, 1] の場合、接頭辞 +1 -1 と -1 +1 はどちらも位置 2 で合計 0 に達するため、そこからの探索は同じです。各結果は初回に保存し、再利用します。
累積合計は -S から S の範囲に収まるため、インデックスとして使えるように S を加算します：memo[i][total + S]。状態数は最大で n × (2S+1) となり、合計が 1000 になる 20 個の数の場合は約 4 × 10^4 で、それぞれの処理は定数時間です。
アルゴリズム
S = sum(nums)を計算し、-1 で埋めたn × (2S+1)のメモを作成します。count(i, total)では、これまでと同様にi == nの基本ケースを返します。memo[i][total + S]が -1 の場合、count(i+1, total + nums[i]) + count(i+1, total - nums[i])を代入します。- 保存された値を返し、
count(0, 0)を呼び出します。
def findTargetSumWays(nums, target):
n = len(nums)
whole = sum(nums)
# memo[i][total + whole]: ways for nums[i:] from this running total, -1 while unknown
memo = [[-1] * (2 * whole + 1) for _ in range(n)]
def count(i, total):
if i == n:
return 1 if total == target else 0
if memo[i][total + whole] == -1:
memo[i][total + whole] = count(i + 1, total + nums[i]) + count(i + 1, total - nums[i])
return memo[i][total + whole]
return count(0, 0)合計が (S + target) / 2 になる部分集合の数を数える
考え方
Pをプラス符号の数の合計、Nをそれ以外の数の合計とします。このとき、P - N = targetかつP + N = Sなので、2P = S + targetとなります。プラス側のグループの合計が(S + target) / 2となるとき、ちょうどその符号の選び方が条件を満たし、そのような部分集合はそれぞれ1つの符号の選び方に対応します。
ways[s]は、これまでに見た数から合計がsになる部分集合の個数を数えます。初期値はways[0] = 1です。数xごとに、合計がsになる部分集合は、xを使わないか、合計がs - xになる部分集合にxを加えるかのどちらかです。sを大きい方から小さい方へ処理すると、ways[s - x]にはまだxを処理する前の値が残るため、同じ数を2回使うことはありません。0の場合は各値を自身に加えるので、すべての個数が2倍になります。これは0に2通りの符号を付けられるためです。加算回数はn × goalで、最大でも2 × 10^4です。
アルゴリズム
S = sum(nums)を計算します。|target| > SまたはS + targetが奇数の場合は、0を返します。goal = (S + target) / 2と設定し、goal + 1個のゼロでwaysを作成し、ways[0] = 1と設定します。numsの各xについて、goalからxまでsを降順に処理し、ways[s - x]をways[s]に加えます。ways[goal]を返します。
def findTargetSumWays(nums, target):
whole = sum(nums)
# plus - minus = target and plus + minus = whole, so plus = (whole + target) / 2
if abs(target) > whole or (whole + target) % 2 == 1:
return 0
goal = (whole + target) // 2
# ways[s]: how many subsets of the values seen so far add up to s
ways = [0] * (goal + 1)
ways[0] = 1
for x in nums:
# From the top down, so each value is used at most once
for s in range(goal, x - 1, -1):
ways[s] += ways[s - x]
return ways[goal]
落とし穴と境界ケース
- 偶奇チェックを省略する。
[6, 3]と目標値 4 の場合、(9 + 4) / 2は切り捨てられて 6 となり、部分集合{6}によって答えが 0 ではなく 1 になる。 - 範囲チェックを省略する。
[1, 2, 3]と目標値 -10 の場合、(6 - 10) / 2 = -2となり、配列サイズが負になる。 waysを下から上へ埋める。すると、ある数が、その数をすでに使っている部分集合に加わってしまう。[1, 3]と目標値 2 の場合、答えが 1 ではなく 2 と報告される。- ゼロを1通りの選択肢として扱う。
[0, 0, 0, 1, 0, 0]と目標値 -1 の場合、5つのゼロそれぞれに符号を割り当てるパターンの数だけ、答えは32通りになる。 - 負の累計値を使ってメモ化配列にインデックスを付ける。すべての累計値に
Sを加えるか、ハッシュマップを使う。
よくある質問3
Target Sum は部分和問題とどのように関係していますか？
プラス符号が付く数の合計は (S + target) / 2 でなければならないため、答えはその合計になる nums の部分集合の数です。部分集合の和を数える動的計画法で解けますが、2つの条件を追加します。値が整数であること、そして |target| が S を超えないことです。
Target Sum の時間計算量はどれくらいですか？
部分集合を数えるDPは、Sをnumsの合計とすると、時間計算量O(n × S)、メモリ計算量O(S)で実行できます。メモ化再帰も時間計算量は同じですが、n × (2S+1)のテーブルを使用します。すべての符号を試す方法はO(2^n)です。
Target Sumは、累積合計を保持するハッシュマップで解けますか？
はい。到達可能な各累積合計について、その合計に到達する符号の接頭辞の数を対応付けます。まず {0: 1} から始め、各数について total + x と total - x から次のマップを作ります。答えは target に対応する数です。これはメモ化再帰を前向きに実行するもので、計算時間は同じ O(n × S) です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def findTargetSumWays(nums, target):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
nums = [2, 1, 1] target = 2
期待される出力
2