Combination Sum アルゴリズム解析

📊 アルゴリズムの全体フロー

入力検証

→

配列ソート

→

バックトラッキング開始

→

解の探索

→

結果返却

🌳 具体例での探索木構造 (candidates=[2,3,6,7], target=7)

Start: [] (target=7)
Choose 2: [2] (target=5)

                                Choose 3: [3] (target=4)
                            
                                Choose 6: [6] (target=1)
                            
                                Choose 7: [7] (target=0) ✅
                            
├─ Choose 2: [2,2] (target=3)

                                ├─ Choose 3: [3,3] (target=1)
                            
                                ├─ Choose 6: [6,6] (target=-5) ❌
                            
                                └─ Choose 7: [6,7] (target=-6) ❌
                            
│ ├─ Choose 2: [2,2,2] (target=1)

                                │ │ └─ Choose 3: [2,2,3] (target=0) ✅
                            
│ └─ Choose 3: [2,3] (target=2)

                                │ └─ Choose 2: [2,3,2] (target=0) - Skip (順序)

⚙️ 主要処理の詳細解析

1. 前処理：ソート

candidates.sort((a, b) => a - b)

目的: 早期終了を可能にする

効果: candidate > remainingTargetで枝刈り

時間計算量: O(N log N)

2. バックトラッキング開始

backtrack(0, [], target)

パラメータ:

startIndex: 0 (最初の要素から)
currentCombination: [] (空配列)
remainingTarget: 7 (目標値)

3. 終了条件チェック

                            if (remainingTarget === 0) { result.push([...currentCombination]);
                            return; }
                        

条件: 残り目標値が0になった時

処理: 現在の組み合わせを結果に追加

4. 枝刈り最適化

if (candidate > remainingTarget) { break; }

条件: 候補値が残り目標値を超過

効果: 以降の探索をスキップ（ソート済みのため）

🔄 再帰呼び出しのスタック構造

例: [2,2,3]の組み合わせ発見まで📱 Call 1: backtrack(0, [], 7)
├─ Choose candidate[0] = 2
├─ Push 2 to combination: [2]

                                └─ 📱 Call 2: backtrack(0, [2], 5)
                            
├─ Choose candidate[0] = 2 again
├─ Push 2 to combination: [2,2]

                                └─ 📱 Call 3: backtrack(0, [2,2], 3)
                            
├─ Choose candidate[1] = 3
├─ Push 3 to combination: [2,2,3]

                                └─ 📱 Call 4: backtrack(1, [2,2,3], 0)
                            

                                ✅ remainingTarget === 0 → Add [2,2,3] to result
                            
🔙 Return from Call 4
🔙 Pop 3 from combination: [2,2]
🔙 Return from Call 3
🔙 Pop 2 from combination: [2]
🔙 Return from Call 2
🔙 Pop 2 from combination: []
Continue with next candidate...

📈 計算量分析

項目	計算量	説明
時間計算量	O(N^(T/M))	N=配列長, T=target値, M=最小候補値
空間計算量	O(T/M)	再帰スタックの最大深度
ソート処理	O(N log N)	一回だけの前処理
最悪ケース探索数	O(2^T)	candidates=[1], target=Tの場合

⚡ パフォーマンス最適化ポイント

1. 早期終了

ソート済み配列により、候補値が目標値を超えた時点で以降の探索を停止

if (candidate > remainingTarget) break;

2. インデックス管理

同一要素の重複使用を許可しつつ、順序を保って重複組み合わせを防止

backtrack(i, ...); // i番目以降から選択

3. メモリ効率

配列の動的構築・削除によりメモリ使用量を最小化

currentCombination.push(candidate); // 処理後 currentCombination.pop();

4. 型安全性

TypeScriptの型システムによりランタイムエラーを防止し、最適化されたコードを生成

🎯 実行例での詳細追跡

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

結果: [[2,2,3], [7]]

Step 1: ソート → [2,3,6,7] (既にソート済み)

Step 2: backtrack(0, [], 7) 開始

Step 3: i=0, candidate=2, 2 ≤ 7 → [2]で再帰

Step 4: i=0, candidate=2, 2 ≤ 5 → [2,2]で再帰

Step 5: i=1, candidate=3, 3 ≤ 3 → [2,2,3]で再帰

Step 6: remainingTarget=0 → [2,2,3]を結果に追加 ✅

Step 7: バックトラック、他の候補を探索...

Step 8: i=3, candidate=7, 7 ≤ 7 → [7]で再帰

Step 9: remainingTarget=0 → [7]を結果に追加 ✅

🔍 Combination Sum アルゴリズム詳細解析