Pythonで＋と−を配置して合計をターゲット値に一致させる方法の数を求めるプログラム

問題の概要

負でない整数のリスト nums と整数 target が与えられます。それぞれの要素に対して「+」または「-」の記号を割り当て、式全体の評価結果が target と一致するような配置が何通りあるかを求めます。

たとえば、入力が nums = [2, 3, 3, 3, 2]、target = 9 の場合、出力は 2 になります。条件を満たすのは次の2通りです。

• -2 + 3 + 3 + 3 + 2
• 2 + 3 + 3 + 3 - 2

考え方：部分和問題への置き換え

この問題は、動的計画法（DP）による「部分集合の数え上げ」として定式化できます。プラス記号を付けた要素の総和を P、マイナス記号を付けた要素の総和の絶対値を N とすると、次の2つの関係式が成り立ちます。

• P - N = target
• P + N = s（s は nums 全体の合計）

両者を連立すると P = (s + target) ÷ 2 が導かれます。つまり「nums から総和が (s + target) ÷ 2 になる部分集合を選ぶ方法の数」を数えれば、それがそのまま答えになります。

解法の手順

1. s ← nums の全要素の合計を求める
2. (s + target) が奇数の場合、または target > s の場合は条件を満たす配置が存在しないので 0 を返す
3. W ← (s + target) ÷ 2 の商（小数点以下切り捨て）
4. サイズ (W + 1) の配列 dp1 を 0 で初期化し、dp1[0] = 1 とする（何も選ばない状態で和 0 が 1 通り作れることを表す）
5. 同じサイズの作業用配列 dp2 も 0 で初期化して用意する
6. nums の各要素 i について、j = 0 ～ W の範囲で j が nums[i] 以上のとき dp2[j] += dp1[j - nums[i]] で更新し、その後 dp1 に dp2 の値を加算して dp2 を 0 に戻す
7. 最後に dp1 の末尾の要素（＝ dp1[W]）を返す

実装例

class Solution:
   def solve(self, nums, target):
      s = sum(nums)

      # 条件を満たす配置が存在しない場合
      if (s + target) % 2 != 0 or target > s:
         return 0

      W = (s + target) // 2

      # 総和が W になる部分集合の個数を数えるDPテーブル
      dp1 = [0] * (W + 1)
      dp1[0] = 1
      dp2 = [0] * (W + 1)

      for i in range(len(nums)):
         for j in range(W + 1):
            if j >= nums[i]:
               dp2[j] += dp1[j - nums[i]]
         for j in range(W + 1):
            dp1[j] += dp2[j]
            dp2[j] = 0

      return dp1[-1]

ob = Solution()
nums = [2, 3, 3, 3, 2]
target = 9
print(ob.solve(nums, target))

入力

[2, 3, 3, 3, 2], 9

出力

2

より簡潔な書き方：1次元DPと逆順ループ

配列を2本使う代わりに、1本の dp 配列を大きい添字から逆順に更新すれば、同じ結果を少ないコード量とメモリで得られます。逆順に走査するのは、同じ要素を一度の処理で重複して数えてしまうのを防ぐためです。

class Solution:
   def solve(self, nums, target):
      s = sum(nums)
      if (s + target) % 2 != 0 or target > s:
         return 0

      W = (s + target) // 2
      dp = [0] * (W + 1)
      dp[0] = 1

      for num in nums:
         for j in range(W, num - 1, -1):
            dp[j] += dp[j - num]

      return dp[W]

計算量

• 時間計算量：O(n × W)（n は nums の要素数、W = (s + target) ÷ 2）
• 空間計算量：O(W)

なお、(s + target) が奇数のときや target の絶対値が s を超えるときは、どのように記号を配置しても target に一致させることができないため、冒頭のチェックで 0 を即座に返しています。