回溯法の基本概念

回溯法（Backtracking）は、探索空間を系統的に調べるアルゴリズム手法です。再帰と密接に関連しており、再帰的な探索過程で「戻る」操作を含むため、この名前が付いています。

この手法の核心は全探索にあります。問題の制約条件を満たすすべての解を列挙し、その中から目的のものを選び出します。効率化のために枝刈り（Pruning）を組み合わせることもありますが、本質的には完全探索である点は変わりません。

適用可能な問題類型

• 組合せ問題: N個の要素から規則に基づいてk個を選ぶ
• 分割問題: 文字列を特定の規則で分割する方法の総数
• 部分集合問題: 条件を満たす部分集合の列挙
• 順列問題: N個の要素の並び方の総数
• 盤面問題: Nクイーン問題、数独の解法など

木構造としての抽象化

回溯法で扱う問題は、すべて木構造として表現可能です。各ノードは選択肢を、階層の深さは探索の進行状況を表します。

集合の要素数が木の広さ（分岐数）、再帰の深さが木の高さに対応します。再帰には必ず終了条件が必要なため、有限高のN叉木として扱えます。

汎用テンプレート

回溯法の実装は以下の3要素で構成されます：

1. 関数定義: 戻り値は通常void、必要な引数を動的に追加
2. 終了条件: 葉ノード到達時に解を記録
3. 探索ループ: 現在の層で選択可能な要素を順に試行

void explore(パラメータ) {
    if (終了条件を満たす) {
        解を記録;
        return;
    }
    
    for (各選択肢について) {
        選択を確定;
        explore(次の状態);  // 深さ優先で進む
        選択を取り消す;      // 状態を復元（回溯）
    }
}

LeetCode 77: 組合せ

問題文

整数nとkが与えられたとき、1からnまでの整数からk個を選ぶすべての組合せを返してください。

入力例: n = 4, k = 2
出力例: [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]

解法の設計

この問題を木構造で捉えると：

• 根ノードは空の状態から始まる
• 各層で未使用の数値から1つ選んで追加
• 左から右へ順に選び、重複を避ける
• 深さkに達した時点で1つの解が完成

探索範囲を制御するためにbeginパラメータを使用し、重複した組合せの生成を防止します。

実装（C++）

class Solution {
    vector<int> current;           // 構築中の組合せ
    vector<vector<int>> answers;  // 完成した組合せの集合
    
    void dfs(int n, int k, int begin) {
        // 終了条件：k個選び終わった
        if (current.size() == k) {
            answers.push_back(current);
            return;
        }
        
        // beginからnまでの数値を候補にする
        for (int num = begin; num <= n; ++num) {
            current.push_back(num);      // 選択を確定
            dfs(n, k, num + 1);           // 次の数値から探索
            current.pop_back();            // 選択を撤回（回溯）
        }
    }
    
public:
    vector<vector<int>> combine(int n, int k) {
        current.clear();
        answers.clear();
        dfs(n, k, 1);
        return answers;
    }
};

探索の流れ（n=4, k=2）

以下のような探索木が展開されます：

              []
           /  |  |  \
          1   2   3   4
         /|\  |\
        2 3 4  3 4
       /
     [1,2] [1,3] [1,4] [2,3] [2,4] [3,4]

各分岐でnum + 1を次の開始位置とすることで、重複を排除しつつ完全な組合せを生成しています。