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

📋 アルゴリズム概要

問題：重複要素を含む配列から、各要素を最大1回使用して目標値に達する全ての一意な組み合わせを見つける

手法：バックトラッキング + ソート + 重複スキップ

🎯 計算量分析

時間計算量： O(2^n) - 最悪の場合、各要素について選ぶ/選ばないの2択

空間計算量： O(target) - 再帰の深さは最大でtargetの値まで

🔄 ステップ1: 配列のソート

1ソート前

元の配列: [10,1,2,7,6,1,5]

10
1
2
7
6
1
5

重複要素(1)が分散している状態

2ソート後

ソート済み: [1,1,2,5,6,7,10]

1
1
2
5
6
7
10

重複要素が隣接し、効率的な剪定が可能

// ソート処理のコード candidates.sort((a, b) => a - b); // 目的: 重複要素を隣接させ、後の重複スキップ処理を効率化

🌳 ステップ2: バックトラッキング探索ツリー

Target = 8 の場合の探索ツリーを可視化:

開始
sum=0
[]
1選択
sum=1
[1]
1スキップ
重複のため
2選択
sum=2
[2]
5選択
sum=5
[5]
1,1選択
sum=2
[1,1]
1,2選択
sum=3
[1,2]
2,5選択
sum=7
[2,5]
5,6選択
sum=11
剪定
1,1,6選択
sum=8
[1,1,6]✓
1,2,5選択
sum=8
[1,2,5]✓
1,7選択
sum=8
[1,7]✓
2,6選択
sum=8
[2,6]✓

🚫 ステップ3: 重複スキップロジック

3重複検出条件

if (i > startIndex && candidates[i] === candidates[i - 1]) { continue; // 同じレベルでの重複をスキップ }

条件解説：

  • i > startIndex: 最初の要素ではない
  • candidates[i] === candidates[i - 1]: 前の要素と同じ値

4スキップの効果

配列 [1,1,2] で target=3 の場合:

スキップなし: [1,2], [1,2] → 重複!

スキップあり: [1,2] → 一意!

同じレベルでの重複要素使用を防ぎ、結果の一意性を保証

🎮 インタラクティブデモ

実際にアルゴリズムの動作を体験してみましょう:

デモを実行するボタンをクリックしてください

⚡ 最適化ポイント

A早期剪定

currentSum > target の場合、即座に探索を中断

ソート済み配列により、以降の要素も必ず target を超えるため効果的

Bメモリ効率

バックトラッキングによる状態復元でメモリ使用量を最小化

currentCombination.push(candidates[i]); // 追加 // 再帰呼び出し currentCombination.pop(); // 復元

C重複排除効率

O(1) 時間での重複検出により、不要な計算を回避

ハッシュセットを使わず、配列の隣接要素比較で実現