【Go】部分和問題（動的計画法）のサンプルコードを書いてみた

概要

• Goで部分和問題を動的計画法で実装
• 部分和問題は与えられた数値の集合から、合計が目標値になる部分集合が存在するかを判定する問題。動的計画法の典型的な応用例の一つ。

特徴

• 効率的計算: 時間計算量O(n×target)で解ける
• メモリトレードオフ: 空間O(n×target)または最適化でO(target)
• 2つのアプローチ: 判定問題と個数カウント
• バックトラック: 実際の解（部分集合）も復元可能
• 実用性: ナップサック問題の基礎となる重要アルゴリズム

部分和問題とは

問題の定義

入力: 整数の配列 nums = [n₁, n₂, ..., nₙ] と目標値 target

出力: nums の部分集合で合計が target になるものが存在するか

具体例

配列: [3, 34, 4, 12, 5, 2]
目標値: 9

解: [4, 5] または [3, 4, 2]
→ 4 + 5 = 9 ✓
→ 3 + 4 + 2 = 9 ✓

応用例

• ナップサック問題
• 予算配分問題
• 硬貨での支払い問題
• パーティション問題（配列を等しい和に分割）
• 組み合わせ最適化

動的計画法のアプローチ

基本的な考え方

部分問題の定義:

dp[i][j] = nums[0..i-1] の要素を使って合計 j を作れるか（true/false）

漸化式:

dp[i][j] = dp[i-1][j]  OR  dp[i-1][j - nums[i-1]]
           ↑                ↑
      使わない場合      使う場合

初期条件:

dp[i][0] = true  （合計0は常に作れる：何も選ばない）
dp[0][j] = false （j > 0の場合、要素がないので作れない）

計算過程の可視化

配列 [3, 4, 5, 2] で目標値 9 の例：

DPテーブル (◯: 作れる, ×: 作れない):
       0   1   2   3   4   5   6   7   8   9
初期   ◯   ×   ×   ×   ×   ×   ×   ×   ×   ×
  3    ◯   ×   ×   ◯   ×   ×   ×   ×   ×   ×
  4    ◯   ×   ×   ◯   ◯   ×   ×   ◯   ×   ×
  5    ◯   ×   ×   ◯   ◯   ◯   ×   ◯   ◯   ◯
  2    ◯   ×   ◯   ◯   ◯   ◯   ◯   ◯   ◯   ◯

結果: dp[4][9] = ◯ → 合計9は作れる ✓

ステップバイステップ

Step 1: 初期状態

• 合計0は常に作れる（何も選ばない）

Step 2: 要素3を追加

• 3が作れるようになる

Step 3: 要素4を追加

• 4が作れる（4単体）
• 7が作れる（3 + 4）

Step 4: 要素5を追加

• 5が作れる（5単体）
• 8が作れる（3 + 5）
• 9が作れる（4 + 5） ← 目標達成！

Step 5: 要素2を追加

• さらに多くの合計が作れる

サンプルコード

基本実装（判定問題）

package main

import "fmt"

// SubsetSum は動的計画法で部分和問題を解く
func SubsetSum(nums []int, target int) bool {
	n := len(nums)

	// dp[i][j]: nums[0..i-1]の要素を使って合計jを作れるか
	dp := make([][]bool, n+1)
	for i := range dp {
		dp[i] = make([]bool, target+1)
	}

	// 初期条件: 合計0は常に作れる（何も選ばない）
	for i := 0; i <= n; i++ {
		dp[i][0] = true
	}

	// ボトムアップで計算
	for i := 1; i <= n; i++ {
		for j := 0; j <= target; j++ {
			// i番目の要素を使わない場合
			dp[i][j] = dp[i-1][j]

			// i番目の要素を使う場合（値がjより小さい場合のみ）
			if j >= nums[i-1] {
				dp[i][j] = dp[i][j] || dp[i-1][j-nums[i-1]]
			}
		}
	}

	return dp[n][target]
}

実際の要素を見つける（バックトラック）

// FindSubsetSum は部分和を作る実際の要素を見つける
func FindSubsetSum(nums []int, target int) []int {
	n := len(nums)
	dp := make([][]bool, n+1)
	for i := range dp {
		dp[i] = make([]bool, target+1)
	}

	for i := 0; i <= n; i++ {
		dp[i][0] = true
	}

	for i := 1; i <= n; i++ {
		for j := 0; j <= target; j++ {
			dp[i][j] = dp[i-1][j]
			if j >= nums[i-1] {
				dp[i][j] = dp[i][j] || dp[i-1][j-nums[i-1]]
			}
		}
	}

	// 解が存在しない場合
	if !dp[n][target] {
		return nil
	}

	// バックトラック: 実際に使った要素を復元
	result := []int{}
	i, j := n, target

	for i > 0 && j > 0 {
		// i番目の要素を使った場合
		if !dp[i-1][j] && j >= nums[i-1] && dp[i-1][j-nums[i-1]] {
			result = append(result, nums[i-1])
			j -= nums[i-1]
		}
		i--
	}

	return result
}

解の個数を数える

// CountSubsetSums は目標値を作る方法の数を数える
func CountSubsetSums(nums []int, target int) int {
	n := len(nums)

	// dp[i][j]: nums[0..i-1]を使って合計jを作る方法の数
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, target+1)
	}

	// 初期条件: 合計0を作る方法は1通り（何も選ばない）
	for i := 0; i <= n; i++ {
		dp[i][0] = 1
	}

	// ボトムアップで計算
	for i := 1; i <= n; i++ {
		for j := 0; j <= target; j++ {
			// i番目の要素を使わない場合
			dp[i][j] = dp[i-1][j]

			// i番目の要素を使う場合
			if j >= nums[i-1] {
				dp[i][j] += dp[i-1][j-nums[i-1]]
			}
		}
	}

	return dp[n][target]
}

空間最適化版（O(target)）

// SubsetSumOptimized は空間計算量を最適化した部分和問題
func SubsetSumOptimized(nums []int, target int) bool {
	// dp[j]: 合計jを作れるか
	dp := make([]bool, target+1)
	dp[0] = true

	for _, num := range nums {
		// 逆順で更新（同じ要素を複数回使わないため）
		for j := target; j >= num; j-- {
			if dp[j-num] {
				dp[j] = true
			}
		}
	}

	return dp[target]
}

重要: 1次元配列で実装する場合、逆順で更新する必要がある。順方向だと同じ要素を複数回使ってしまう。

// ✗ NG: 順方向 → 同じ要素を複数回使う
for j := num; j <= target; j++ {
    dp[j] = dp[j] || dp[j-num]
}

// ✓ OK: 逆順 → 各要素を1回だけ使う
for j := target; j >= num; j-- {
    dp[j] = dp[j] || dp[j-num]
}

計算量

時間計算量

実装方法	時間計算量	説明
全探索（ビット演算）	O(2^n)	すべての部分集合を調べる
2次元DP	O(n × target)	n個の要素×targetまでの値
1次元DP（最適化）	O(n × target)	同上

空間計算量

実装方法	空間計算量	説明
全探索	O(n)	再帰スタック
2次元DP	O(n × target)	dpテーブル
1次元DP（最適化）	O(target)	1次元配列のみ

パフォーマンス比較

配列サイズ n=20, target=1000 の場合:

全探索:       約1秒（2^20 = 100万回の計算）
2次元DP:      約0.001秒（20×1000 = 2万回の計算）
最適化DP:     約0.001秒（同上、メモリは1/20）

動作原理の詳細

なぜ漸化式が成り立つか

dp[i][j] を計算する際、nums[i-1] を使うか使わないかの2択：

1. 使わない場合

• nums[0..i-2] で合計 j を作れればOK
• → dp[i][j] = dp[i-1][j]

2. 使う場合

• nums[0..i-2] で合計 j - nums[i-1] を作れればOK
• そこに nums[i-1] を足せば j になる
• → dp[i][j] = dp[i-1][j - nums[i-1]]

どちらか一方でも可能なら dp[i][j] = true

バックトラックの仕組み

dpテーブル構築後、逆順に辿って実際の解を復元：

配列: [3, 4, 5, 2], 目標: 9

dpテーブルから逆順に辿る:
i=4, j=9: nums[3]=2 を使ったか？
  → dp[3][9]=true なので使わない

i=3, j=9: nums[2]=5 を使ったか？
  → dp[2][9]=false, dp[2][4]=true なので使う！
  → j = 9 - 5 = 4

i=2, j=4: nums[1]=4 を使ったか？
  → dp[1][4]=false, dp[1][0]=true なので使う！
  → j = 4 - 4 = 0

i=1, j=0: 終了

解: [5, 4]

使いどころ

向いてる場面

• ナップサック問題: 重さと価値のある品物を選ぶ
• 予算配分: 限られた予算で目標額を達成
• 組み合わせ最適化: 複数の選択肢から最適な組み合わせ
• パーティション問題: 配列を等しい和に分割できるか

実例1: 硬貨での支払い

func canPayExactly(coins []int, price int) bool {
    return SubsetSum(coins, price)
}

// 使用例
coins := []int{1, 5, 10, 25, 50, 100}
price := 87

if canPayExactly(coins, price) {
    subset := FindSubsetSum(coins, price)
    fmt.Printf("87円の支払い: %v円硬貨\\n", subset)
    // 例: [50, 25, 10, 1, 1] など
}

実例2: 配列の分割（Equal Partition）

配列を等しい和の2グループに分けられるか：

// CanPartition は配列を等しい和に分割できるか判定
func CanPartition(nums []int) bool {
    sum := 0
    for _, num := range nums {
        sum += num
    }

    // 合計が奇数なら分割不可能
    if sum%2 != 0 {
        return false
    }

    // 半分の値を作れるか？
    return SubsetSum(nums, sum/2)
}

// 使用例
nums := []int{1, 5, 11, 5}
// 合計 = 22, 半分 = 11
// [1, 5, 5] と [11] に分割可能 → true

実例3: ターゲットサム問題

配列の各要素に+または-を付けて目標値を作る：

// FindTargetSumWays は目標値を作る方法の数
func FindTargetSumWays(nums []int, target int) int {
    sum := 0
    for _, num := range nums {
        sum += num
    }

    // 不可能な場合
    if sum < target || (sum+target)%2 != 0 {
        return 0
    }

    // P - N = target かつ P + N = sum
    // → P = (sum + target) / 2
    // Pの部分集合を作る方法の数を求める
    return CountSubsetSums(nums, (sum+target)/2)
}

関連する問題

1. 0/1ナップサック問題

部分和問題の発展版（価値の概念を追加）：

// Knapsack は0/1ナップサック問題を解く
func Knapsack(weights []int, values []int, capacity int) int {
    n := len(weights)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, capacity+1)
    }

    for i := 1; i <= n; i++ {
        for w := 0; w <= capacity; w++ {
            // 入れない場合
            dp[i][w] = dp[i-1][w]

            // 入れる場合
            if w >= weights[i-1] {
                value := dp[i-1][w-weights[i-1]] + values[i-1]
                if value > dp[i][w] {
                    dp[i][w] = value
                }
            }
        }
    }

    return dp[n][capacity]
}

2. 完全部分和問題（無制限使用可）

各要素を何回でも使える場合：

// SubsetSumUnlimited は要素を無制限に使える部分和問題
func SubsetSumUnlimited(nums []int, target int) bool {
    dp := make([]bool, target+1)
    dp[0] = true

    // 順方向で更新（同じ要素を複数回使えるため）
    for j := 1; j <= target; j++ {
        for _, num := range nums {
            if j >= num && dp[j-num] {
                dp[j] = true
                break
            }
        }
    }

    return dp[target]
}

3. 最小要素数の部分和

目標値を作る最小の要素数：

// MinSubsetSum は目標値を作る最小要素数
func MinSubsetSum(nums []int, target int) int {
    dp := make([]int, target+1)
    for i := range dp {
        dp[i] = target + 1 // 十分大きい値
    }
    dp[0] = 0

    for _, num := range nums {
        for j := target; j >= num; j-- {
            dp[j] = min(dp[j], dp[j-num]+1)
        }
    }

    if dp[target] > target {
        return -1 // 不可能
    }
    return dp[target]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

最適化テクニック

1. 早期終了

目標値に到達したら計算を打ち切る：

func SubsetSumEarlyExit(nums []int, target int) bool {
    dp := make([]bool, target+1)
    dp[0] = true

    for _, num := range nums {
        for j := target; j >= num; j-- {
            if dp[j-num] {
                dp[j] = true
                if j == target {
                    return true // 早期終了
                }
            }
        }
    }

    return dp[target]
}

2. 事前ソート

配列をソートして枝刈り：

import "sort"

func SubsetSumPruned(nums []int, target int) bool {
    sort.Ints(nums)

    // 合計が目標値未満なら不可能
    sum := 0
    for _, num := range nums {
        sum += num
    }
    if sum < target {
        return false
    }

    // 最大値が目標値を超える要素は除外
    validNums := []int{}
    for _, num := range nums {
        if num <= target {
            validNums = append(validNums, num)
        }
    }

    return SubsetSum(validNums, target)
}

3. ビットセット最適化

ビット演算で高速化（targetが小さい場合）：

// SubsetSumBitset はビットセットを使った高速化版
func SubsetSumBitset(nums []int, target int) bool {
    // dp を uint64 のビットで表現（target < 64の場合）
    if target >= 64 {
        return SubsetSum(nums, target)
    }

    var dp uint64 = 1 // dp[0] = true

    for _, num := range nums {
        if num < 64 {
            dp |= dp << uint(num)
        }
    }

    return (dp & (1 << uint(target))) != 0
}

デバッグとテスト

テストケース

func TestSubsetSum() {
    testCases := []struct {
        nums   []int
        target int
        want   bool
    }{
        {[]int{3, 34, 4, 12, 5, 2}, 9, true},     // [4, 5]
        {[]int{3, 34, 4, 12, 5, 2}, 30, false},   // 不可能
        {[]int{1, 2, 3, 7}, 6, true},             // [1, 2, 3]
        {[]int{1, 2, 7, 1, 5}, 10, true},         // [1, 2, 7]
        {[]int{1, 5, 11, 5}, 11, true},           // [1, 5, 5]
        {[]int{2, 4, 6}, 5, false},               // 奇数は作れない
    }

    for _, tc := range testCases {
        got := SubsetSum(tc.nums, tc.target)
        if got != tc.want {
            fmt.Printf("FAIL: nums=%v, target=%d, got=%v, want=%v\\n",
                tc.nums, tc.target, got, tc.want)
        }
    }
}

デバッグ用可視化

// PrintDPTable はdpテーブルを見やすく表示
func PrintDPTable(dp [][]bool, nums []int, target int) {
    fmt.Print("     ")
    for j := 0; j <= target; j++ {
        fmt.Printf("%3d", j)
    }
    fmt.Println()

    for i := 0; i < len(dp); i++ {
        if i == 0 {
            fmt.Print("初期 ")
        } else {
            fmt.Printf("%3d  ", nums[i-1])
        }
        for j := 0; j <= target; j++ {
            if dp[i][j] {
                fmt.Print("  ◯")
            } else {
                fmt.Print("  ×")
            }
        }
        fmt.Println()
    }
}

まとめ

メリット

• 時間計算量O(n×target)で効率的
• 解の存在判定だけでなく、実際の解や解の個数も求められる
• 空間を最適化してO(target)に削減可能
• ナップサック問題の基礎となる重要アルゴリズム
• 実用的な応用が多い

デメリット

• targetが大きいとメモリと時間が問題に
• 浮動小数点数には適用できない
• targetが非常に大きい場合は別のアプローチが必要

使うべき時

• 判定問題: 特定の合計を作れるか
• 組み合わせ最適化: 複数の選択肢から最適な組み合わせ
• ナップサック系問題: 容量制約のある選択問題
• パーティション問題: 配列の分割

targetの大きさによる選択

targetの範囲	推奨実装	理由
target < 1000	1次元DP	十分高速かつ省メモリ
1000 ≤ target < 10^5	1次元DP	メモリ効率重視
target ≥ 10^5	別手法検討	Meet-in-the-middle など
n < 20	ビット全探索も可	実装がシンプル

部分和問題は動的計画法の典型問題であり、ナップサック問題や組み合わせ最適化の基礎となる。dpテーブルの構築、漸化式の立て方、バックトラックによる解の復元など、DPの重要な概念を学ぶのに最適なアルゴリズム。