部分和問題（Subset Sum Problem）は、次のように定義される典型的な 動的計画法（DP） の問題です。
N枚のカードがあり、それぞれに整数A[i]が書かれています。
これらの中からいくつかを選んで、その合計をSにできるかを判定してください。
N S
A1 A2 A3 ... AN
Sを作れるなら"Yes"- 作れないなら
"No"
各カードに対して、「選ぶ」or「選ばない」 の2択を試す。
状態を記録しながら解く ことで、同じ計算を繰り返さないようにする。
- 現在のカードを選ぶ
- 現在のカードを選ばない
- 残りのカードで
Sを作れるかを再帰的に判定
function subsetSumRecursive(N, S, A, index = 0, sum = 0) {
// ベースケース: 合計が S になったら成功
if (sum === S) return true;
// カードをすべて使ったら終了
if (index >= N) return false;
// カード index を選ばない場合
if (subsetSumRecursive(N, S, A, index + 1, sum)) return true;
// カード index を選ぶ場合
if (subsetSumRecursive(N, S, A, index + 1, sum + A[index])) return true;
return false;
}
// 入力例
const N = 4,
S = 11;
const A = [3, 1, 4, 5];
console.log(subsetSumRecursive(N, S, A) ? 'Yes' : 'No');O(2^N)（指数時間） →N ≤ 20ならOK、N > 20は厳しい！
DPテーブル dp[i][j] を用意して、以下の遷移を考える。
dp[i][j] = trueの場合、i枚目までのカードを使ってjを作れるdp[i][j]の更新方法：dp[i+1][j] = dp[i][j]（カードを使わない場合）dp[i+1][j + A[i]] = dp[i][j]（カードを使う場合）
function subsetSumDP(N, S, A) {
let dp = Array.from({ length: N + 1 }, () => Array(S + 1).fill(false));
dp[0][0] = true; // 何も選ばない場合、0は作れる
for (let i = 0; i < N; i++) {
for (let j = 0; j <= S; j++) {
if (dp[i][j]) {
dp[i + 1][j] = true; // カードを使わない場合
if (j + A[i] <= S) {
dp[i + 1][j + A[i]] = true; // カードを使う場合
}
}
}
}
return dp[N][S] ? 'Yes' : 'No';
}
// 入力例
const N = 4,
S = 11;
const A = [3, 1, 4, 5];
console.log(subsetSumDP(N, S, A));O(N × S)→N ≤ 60, S ≤ 10000でも間に合う！
N ≤ 60ならば、ビットマスク（bitset） を使ってO(N × log S)にできる！- ビット演算を使って可能な合計を更新する。
function subsetSumBitset(N, S, A) {
let possible = 1n; // ビットセットを整数で管理 (BigInt)
for (let i = 0; i < N; i++) {
possible |= possible << BigInt(A[i]); // 新しい和を追加
}
return (possible & (1n << BigInt(S))) !== 0n ? 'Yes' : 'No';
}
// 入力例
const N = 4,
S = 11;
const A = [3, 1, 4, 5];
console.log(subsetSumBitset(N, S, A));O(N log S)（非常に高速）bitsetを使うことでS ≤ 10^7でも処理可能！
| 解法 | 計算量 | メリット | デメリット |
|---|---|---|---|
| 再帰（バックトラッキング） | O(2^N) |
実装が簡単 | N > 20 で遅い |
| 動的計画法（DP） | O(N × S) |
N = 60 でも可能 |
S が大きいとメモリを消費 |
| ビットマスク（bitset） | O(N log S) |
超高速 (S = 10^7 も可能) |
S が大きいと計算できない |
おすすめの選び方
N ≤ 20→ 再帰（バックトラッキング）N ≤ 60, S ≤ 10000→ 動的計画法（DP）Sが超大きい (10^7など) → ビットマスク（bitset）
✅ 部分和問題は「選ぶ or 選ばない」の2択を考える！
✅ N ≤ 20 なら再帰、N ≤ 60, S ≤ 10000 なら DP、S が超大きいならビットマスク！
✅ O(N × S) で十分高速、bitset で更に最適化できる！