0Pricing
Coding Interview Prep · レッスン

正負の符号を使うTarget Sum

target-sumの割り当て問題を部分集合の和の差に関するナップサックへ変換し、O(n × sum)時間で解きます。

「正負の符号を使うTarget Sum」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

Target Sum 問題

整数配列 nums と整数 target が与えられたとき、各数値に + または - の符号を割り当て、計算結果が target になるようにします。そのような割り当て方の個数を返します。たとえば、nums=[1,1,1,1,1]、target=3 の場合、5通りあります（異なる位置から4つの要素を正にし、1つを負にします）。

全探索：DFSによる列挙

DFSでは各数値に + または - のいずれかを割り当てて再帰的に処理し、target に到達した葉ノードの個数を返します。これは正しい方法ですが、O(2^n) の時間計算量を持つ指数時間アルゴリズムです。n=20 では、再帰呼び出しが100万回を超えます。面接では、まずDFSの方法に触れてから、すぐにDPによる最適化へ話を移すとよいでしょう。

def findTargetSumWays_dfs(nums, target):
    count = [0]
    
    def dfs(i, current_sum):
        if i == len(nums):
            if current_sum == target:
                count[0] += 1
            return
        dfs(i+1, current_sum + nums[i])
        dfs(i+1, current_sum - nums[i])
    
    dfs(0, 0)
    return count[0]

print(findTargetSumWays_dfs([1,1,1,1,1], 3))  # 5

メモ化したDFS

DFSにメモ化を追加します。状態は (index, current_sum) です。current_sum は -total から +total までの範囲を取り得るため、異なる状態は O(n × total) 個あります。メモ化すると、DFSは時間・空間ともに O(n × total)で実行できます。これは有効で面接でも使える方法ですが、変換に基づくDPのほうがより洗練されており、空間効率にも優れています。

from functools import lru_cache

def findTargetSumWays_memo(nums, target):
    total = sum(nums)
    
    @lru_cache(maxsize=None)
    def dp(i, remaining):
        if i == len(nums):
            return 1 if remaining == 0 else 0
        return dp(i+1, remaining - nums[i]) + dp(i+1, remaining + nums[i])
    
    return dp(0, target)

print(findTargetSumWays_memo([1,1,1,1,1], 3))  # 5

数学的な変換

+ を割り当てた数値の集合を P、- を割り当てた集合を N とします。このとき、sum(P) - sum(N) = target かつ sum(P) + sum(N) = total です。両辺を加えると、2 × sum(P) = target + total となるため、sum(P) = (target + total) / 2 です。したがって、この問題は(target + total) / 2 の合計になる nums の部分集合の個数を数える問題に還元できます。これはまさに、0/1ナップサックの「部分集合を数える」バリエーションです。

# sum(P) - sum(N) = target
# sum(P) + sum(N) = total
# => 2*sum(P) = target + total
# => sum(P) = (target + total) / 2
# Count subsets with sum = new_target = (target + total) // 2
print('Reduction: count subsets summing to (target + total) // 2')

DPの前に行う妥当性チェック

DPを実行する前に、次を確認します。(1) target + total は偶数でなければなりません（そうでなければ sum(P) が整数にならず、実現不可能です）。(2) abs(target) > total なら、すべての符号を同じ向きにしても target に到達できません。どちらかのチェックに失敗したら、すぐに 0 を返します。これらのチェックにより、DPループ内で特別な場合分けをせずにエッジケースをきれいに処理できます。

def findTargetSumWays(nums, target):
    total = sum(nums)
    if (target + total) % 2 != 0:
        return 0  # sum(P) would be non-integer
    if abs(target) > total:
        return 0  # impossible to reach
    new_target = (target + total) // 2
    # Count subsets summing to new_target
    dp = [0] * (new_target + 1)
    dp[0] = 1
    for num in nums:
        for c in range(new_target, num - 1, -1):
            dp[c] += dp[c - num]
    return dp[new_target]

print(findTargetSumWays([1,1,1,1,1], 3))  # 5

小さな例を追って確認する

nums=[1,1,1,1,1]、target=3 の場合、total=5、new_target=(3+5)//2=4 です。[1,1,1,1,1] から合計4になる部分集合の個数を数えます。これは C(5,4)=5 です（5つの1から4つを正にし、残りの1つを負にすると、1+1+1+1-1=3 になります）。DPは正しく 5 を返します。この変換により、符号割り当ての問題を標準的な部分集合の個数を数える問題へ、簡潔に対応付けられます。

nums 内の 0 の処理

nums に 0 が含まれている場合、0 に + と - のどちらを割り当てても合計は変わりません。0 が1つあるごとに、有効な割り当ての個数は2倍になります。DPはこれを自然に処理できます。num=0 を処理すると、内部ループ range(new_target, -1, -1) は new_target から 0 まで実行され、dp[c] += dp[c - 0] = dp[c] によって到達可能なすべての合計値が2倍になります。range(new_target, num-1, -1) を使えば、num=0 のときに new_target から 0 まで実行されるため、特別な処理は必要ありません。

# With zeros: each zero doubles the count
print(findTargetSumWays([0, 0, 1], 1))  # 4
# Assignments: +0+0+1, +0-0+1, -0+0+1, -0-0+1 = all give sum 1

計算量の比較

全探索のDFSはO(2^n)です。メモ化したDFSは、時間・空間ともにO(n × total)です。変換に基づく1次元DPは、new_target ≤ total としたとき、時間 O(n × new_target)、空間 O(new_target)です。1次元DPでは変換によって index の次元を破棄できるため、メモ化よりも必要な空間が大幅に少なくなります。

他のナップサック問題との関連

Target Sum は、複数のナップサックの概念を結び付けます。最初は割り当て問題ですが、部分和問題（Partition Equal Subset Sum など）に変換され、同じ0/1ナップサックの後ろ向き反復テンプレートを、個数のカウント（Coin Change II など）に使います。こうした関連性を身につけると、既知のパターンとの構造的な類似性によって、面接で新しい問題をすばやく分類できるようになります。

エッジケースと面接でのポイント

重要なケースは次のとおりです。(1) target = total：すべて正にする1通りだけです。(2) target = -total：すべて負にする1通りだけです。(3) すべて0で target = 0：答えは 2^n です。(4) total が非常に大きく n が小さい場合 — 1次元DP配列のサイズは total/2 によって上限が決まります。面接では、コードを書く前に変換手順を言葉で説明しましょう。そこが、優れた候補者を分ける見えにくい重要ポイントです。

変換を使わない2次元DPの方法

変換を使わない場合、最初の i 個の数値に符号を割り当て、合計 s に到達する方法の数を dp[i][s] と定義します。合計は負になる可能性があるため、total をオフセットとして使い、dp[i][s + total] を利用します。これには (n+1) × (2*total+1) サイズの2次元テーブルが必要です。正しい方法ではありますが、変換後の1次元ナップサックDPよりも多くの空間を使い、面接中に素早く実装するのも難しくなります。

理解度チェック

このレッスンで扱った Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。

レッスンのまとめ

このレッスンでは、Target Sum は符号の割り当てを (target + total) / 2 の合計になる部分集合の個数を数える問題に変換できること、1次元0/1ナップサックの後ろ向き反復で、O(n × new_target) 時間、O(new_target) 空間で部分集合の個数を数えられること、そして早期の妥当性チェック（奇数の合計、|target| > total）によって不要なDPの実行を防げることを学びました。次はダイクストラ法と優先度付きキューを使う、最短経路の領域に進みます。

よくある質問

「正負の符号を使うTarget Sum」レッスンは無料ですか？

はい。「正負の符号を使うTarget Sum」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

「正負の符号を使うTarget Sum」で何を学びますか？

target-sumの割り当て問題を部分集合の和の差に関するナップサックへ変換し、O(n × sum)時間で解きます。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。

「正負の符号を使うTarget Sum」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. 0/1ナップサックと空間最適化
  2. 非有界ナップサックとCoin Change II
  3. Partition Equal Subset Sum
  4. 正負の符号を使うTarget Sum
← Coding Interview Prepに戻る