問題
0 以上のnums と、target をnums の+ か - のtarget に
- どの
数にも、 必ずどちらかの 符号を 1 つ付けます。 数の 順番は 変えません - 同じ値の
数でも、 位置が 違えば 別の 数として 数えます。 0 に +を付けるのと -を付けるのも、 別の 付け方として数えます numsの長さは 1 以上 20 以下、 値は どれも 0 以上 1000 以下で、 全部の 合計は 1000 以下です targetは -1000 以上 1000 以下です
入力と出力の例
例 1
-2 -3 +5 と +2 +3 -5 の 2 通りです。
入力
nums = [2, 3, 5]
target = 0出力
2例 2
どちらかの 1 にだけ + を、
入力
nums = [1, 2, 1, 2]
target = 0出力
4例 3
4 と 6 に
入力
nums = [4, 6]
target = 3出力
0面接での聞かれ方
面接では、
- 「各数に + か - を
付けて、 目標に なる 付け方の 数を 返してください」 - 全部試す
書き方を 出すと 「数が 20 個なら 何通りですか？ 100 個なら？」と、 手間の 増え方を 聞かれます - 「+ を
付けた 数の 合計だけで、 答えが 決まりませんか？」と、 言い 換えの 手が かりを 出される こともあります
0 が
アルゴリズムのチートシートの「動的計画法 (DP)」に、この型の要点を表とコードでまとめています。
まず
段 1
まずは
段 2
付け方をtarget で、target をtarget のtarget のtarget の
段 3
和ごとのways にways[0] = 1 (何もways[s-x] を
解答
Python
Python
def sign_ways(nums, target):
total = sum(nums)
if abs(target) > total:
return 0
if (total + target) % 2:
return 0
want = (total + target) // 2
ways = [0] * (want + 1)
ways[0] = 1
for x in nums:
s = want
while s >= x:
ways[s] += ways[s-x]
s -= 1
return ways[want]JavaScript
JavaScript
function signWays(
nums, target
) {
let total = 0;
for (const x of nums) {
total += x;
}
if (target > total) return 0;
if (-target > total) return 0;
const sum = total + target;
if (sum % 2 !== 0) return 0;
const want = sum / 2;
const ways = Array(want + 1)
.fill(0);
ways[0] = 1;
for (const x of nums) {
let s = want;
while (s >= x) {
ways[s] += ways[s - x];
s--;
}
}
return ways[want];
}Go
Go
func signWays(
nums []int, target int,
) int {
total := 0
for _, x := range nums {
total += x
}
if target > total {
return 0
}
if target < -total {
return 0
}
sum := total + target
if sum%2 != 0 {
return 0
}
want := sum / 2
ways := make([]int, want+1)
ways[0] = 1
for _, x := range nums {
for s := want; s >= x; s-- {
ways[s] += ways[s-x]
}
}
return ways[want]
}target のtotal + target は 0 以上ways[s] にways[s] を
計算量
- 時間は O(n × P) です (P は + を
付ける 数の 合計で、 全部の 合計以下)。 数ごとに 表を 1 回なめます。 20 個で 合計 1000 なら、 2 万回ほどです - 使う
記憶は O(P) です。 表 waysの長さが P + 1 です - 全部試す再帰は
時間が O(2ⁿ) です。 「何番目までで 和が いくつか」を メモする 書き方は O(n × S) の 時間と 記憶で、 言い 換えた 表の 方が 記憶を 小さくできます
よく
- 表を
小さい ほうから回す。 for s in range(x, want + 1)の向きに すると、 同じ数を 何回でも 使う 数え方に なります。 例 2 では、 同じ 位置の 1 を 何回も 使う 選び方まで 数えて、 4 ではなく 8 を返します - 奇数の
場合を落とす。 S と targetの和が 奇数の とき、 P は 整数に なりません。 そのまま 切り捨てて 数えると、 例 3 で 0 でない 数を返します - target が
大きすぎる 場合を落とす。 targetの絶対値が 合計より 大きいと、 P が 負に なったり 表の 外を 指したりします。 Python では 負の 番号が 表の 後ろを 読んでしまい、 エラーに ならずに外れます - 0 を 1 通りと数える。
nums = [0]、target = 0の答えは 2 です。 表の 書き方なら 自然に 2 倍に なるので、 0 を 特別に 飛ばさない ことが大切です
解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日
面接での
書き始める
「全部試すと 2 の n 乗通りです。
+ を 付けた 数の 合計を P と すると、 P は 全部の 合計と 目標を 足して 2 で 割った 数に 決まるので、 和が ちょうど P に なる 選び方を 数える 問題に 言い 換えます。 表を 1 次元に して、 各数で 和の 大きい ほうから 足していけば、 時間は O(n × P)、 記憶は O(P) です。」
書き終えたら、
「例 1 の
[2, 3, 5]で目標 0 を たどります。 合計は 10 なので P は 5 です。 2 を 入れると 和 2 が 1 通り、 3 を 入れると 和 3 と 和 5 が 1 通りずつ、 5 を 入れると 和 5 が 2 通りに なります。 2 と 3 を 選ぶか、 5 だけを 選ぶかの 2 通りで、 答えは 2 です。」