バックトラック法の基本概念

バックトラック法は探索手法の一種で、再帰処理と密接に関連しています。再帰処理を行う際には必ずバックトラックが発生するため、バックトラックは再帰の副産物と言えます。

バックトラック法の効率性

バックトラック法は本質的に全探索アルゴリズムであり、効率的とは言えません。ただし、枝刈り(pruning)を適用することで多少の効率改善が可能です。それでも根本的な全探索の性質は変わりません。

適用可能な問題領域

• 組み合わせ問題: N個の要素からk個を選択する問題
• 分割問題: 文字列の分割方法を求める問題
• 部分集合問題: 与えられた集合の部分集合を求める問題
• 順列問題: 要素の並べ方を求める問題
• 盤面問題: Nクイーン問題や数独など

組み合わせと順列の違いに注意が必要です。組み合わせは要素の順序を考慮せず、順列は順序を考慮します。

バックトラック法の実装パターン

void backtrack(パラメータ) {
    if (終了条件) {
        結果を保存;
        return;
    }

    for (選択: 現在の選択肢) {
        ノード処理;
        backtrack(新しいパラメータ); // 再帰呼び出し
        処理の取り消し; // バックトラック
    }
}

組み合わせ問題の解法

与えられた整数nとkに対して、1からnまでの数からk個を選ぶ全ての組み合わせを求めます。

実装例

class Solution {
private:
    vector<vector<int>> res;
    vector<int> current;
    
    void findCombinations(int n, int k, int start) {
        if (current.size() == k) {
            res.push_back(current);
            return;
        }
        
        for (int i = start; i <= n; ++i) {
            current.push_back(i);
            findCombinations(n, k, i + 1);
            current.pop_back();
        }
    }
    
public:
    vector<vector<int>> combine(int n, int k) {
        findCombinations(n, k, 1);
        return res;
    }
};

この実装では、startパラメータが重複しない組み合わせを生成するために使用されています。各再帰呼び出しで開始インデックスを増やすことで、同じ要素を複数回使用するのを防ぎます。

処理の流れ

1. currentに要素を追加
2. 再帰的に次の要素を探索
3. currentから要素を削除（バックトラック）