🔍 Combination Sum Algorithm Analysis

📊 アルゴリズム概要

1
問題設定: 配列 candidates = [2,3,6,7], target = 7 の場合を例に解析

🏗️ 初期化フェーズ

Step 1: 配列のソート

ソート前:

2
3
6
7
→

ソート後:

2
3
6
7

効果: 小さい数から試すことで早期終了が可能

🌳 DFS探索木の可視化

Level 0 (root): target=7, startIndex=0
開始
[7]
Level 1: 各候補を試行
2を選択
[5]
3を選択
[4]
6を選択
[1]
7を選択
[0] ✓
Level 2: 2を選択した場合の展開
2,2を選択
[3]
2,3を選択
[2]
2,6を選択
[-1] ✗
Level 3: さらなる展開
2,2,3を選択
[0] ✓
2,2,6を選択
[-3] ✗

🔄 バックトラッキングの動作

探索パスの詳細トレース

Path 1: [] → [2] → [2,2] → [2,2,3] → target達成! → バックトラック
Path 2: [] → [2] → [2,2] → [2,2,6] → 無効(sum>target) → バックトラック
Path 3: [] → [2] → [2,3] → [2,3,3] → 無効(sum>target) → バックトラック
Path 4: [] → [7] → target達成! → 解を記録

⚡ 最適化技法

1
早期終了 (Pruning):
if (candidate > remainingTarget) { break; // ソート済みなので以降も全て無効 }
2
重複回避: startIndexにより同じ組み合わせの重複を防止
3
メモリ効率: スプレッド演算子による効率的な配列コピー

📈 計算量解析

時間計算量: O(N^(T/M))

• N: 候補の数 (4)

• T: target値 (7)

• M: 最小候補値 (2)

• 実際の計算: 4^(7/2) ≈ 4^3.5 ≈ 128 (理論上限)

空間計算量: O(T/M)

• 再帰スタックの最大深度

• 実際の計算: 7/2 ≈ 4レベル

🎯 インタラクティブデモ

結果がここに表示されます...

🔍 実装のキーポイント

// TypeScript実装の重要部分 function dfs(startIndex: number, remainingTarget: number): void { // ベースケース: 目標達成 if (remainingTarget === 0) { result.push([...currentCombination]); return; } for (let i = startIndex; i < candidates.length; i++) { const candidate=candidates[i]; // 早期終了による最適化 if (candidate > remainingTarget) break; // 選択 currentCombination.push(candidate); // 再帰 (同じインデックスから開始 = 同じ数字を再利用可能) dfs(i, remainingTarget - candidate); // バックトラッキング currentCombination.pop(); } }

✅ 実行結果の検証

Input: candidates = [2,3,6,7], target = 7

Output: [[2,2,3], [7]]

解1: [2,2,3]
2+2+3 = 7 ✓
解2: [7]
7 = 7 ✓