1.バックトラッキングの理論的基礎

1.1バックトラッキングとは何か

バックトラッキングは探索アルゴリズムの一種であり、再帰処理に基づいて動作します。 再帰呼び出しの結果としてバックトラッキングが発生するため、再帰があれば必ずバックトラッキングも存在します。

1.2バックトラッキングの性能

バックトラッキングは計算効率が悪いという特徴があります。これは、すべての可能性を試す「ブルートフォース」アプローチを採用しているためです。最適化として剪定（枝刈り）を適用することは可能ですが、根本的なアルゴリズムの性質は変わりません。なぜこのような非効率な方法が使われるのかというと、他の効率的な解決策がない場合や、問題を直接解くのが困難な場合に限って使われるからです。

1.3バックトラッキングで扱える問題の種類

バックトラッキングは以下の問題に応用できます：

• 組み合わせ問題：N個の数字の中からK個を選ぶ組み合わせを求める
• 分割問題：文字列を特定のルールに従って分割する方法を求める
• 部分集合問題：N個の要素を持つ集合の条件に合う部分集合の数を求める
• 順列問題：N個の数字を並び替えて作れる順列の数を求める
• チェス盤問題：Nクイーン問題や数独など

バックトラッキングの理解方法

バックトラッキングは木構造で表現できます。これはすべてのバックトラッキング問題が木構造に落とし込めるということを意味します。 集合内の再帰探索を行う際、集合のサイズが木の幅となり、再帰の深さが木の高さとなります。 再帰には終了条件が必要なので、有限の高さを持つN分木になります。

1.4バックトラッキングのテンプレート

バックトラッキングの基本構造は以下の通りです：

• バックトラッキング関数の戻り値と引数

一般的には関数名をbacktrackingと命名します。戻り値は通常voidです。 引数は二分木の再帰と異なり、一度に確定することが難しいため、実装しながら必要なものを追加していきます。 以下のような擬似コードで表されます：

void backtracking(引数)

• 終了条件

木構造では、葉ノードに到達した時点で答えが見つかるため、その場合に結果を保存して再帰を終了します。 終了条件の疑似コードは：

if (終了条件) {
    結果を保存;
    戻る;
}

• 探索の流れ

再帰的に探索を行う際に、現在のノードの子要素を順番に確認します。 この探索の疑似コードは：

for (選択肢: 現在のノードの子要素数) {
    ノードを処理;
    backtracking(経路, 選択リスト); // 再帰呼び出し
    戻す（処理の取り消し）
}

for文は兄弟ノードの探索、再帰呼び出しは深さ方向の探索として考えられます。 全体の木構造を探索するためのテンプレートは：

void backtracking(引数) {
    if (終了条件) {
        結果を保存;
        戻る;
    }

    for (選択肢: 現在のノードの子要素数) {
        ノードを処理;
        backtracking(経路, 選択リスト); // 再帰呼び出し
        戻す（処理の取り消し）
    }
}

2.組み合わせ問題

2.1組み合わせ

問題リンク

• グローバル変数を使用

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(int n, int k, int startIndex) {
        if (path.size() == k) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) { // 最適化ポイント
            path.push_back(i); // ノードの処理
            backtracking(n, k, i + 1);
            path.pop_back(); // 戻す（処理の取り消し）
        }
    }
public:

    vector<vector<int>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }
};

• 引数を通じて値を渡す

class Solution {
public:
    void backtracing(int node, int n, int k, vector<vector<int>>& res, vector<int>& vec)
    {
        // 終了条件
        if (vec.size() == k)
        {
            res.push_back(vec);
            return;
        }
        // 再帰処理
        for(int i = node; i <= n; i++)
        {
            vec.push_back(i);
            backtracing(i + 1, n, k, res, vec);
            // 戻す
            vec.pop_back();
        }


    }
    vector<vector<int>> combine(int n, int k) 
    {
        vector<vector<int>> res;
        vector<int> vec;
        backtracing(1, n, k , res, vec);

        return res;
    }
};

2.2和が指定された組み合わせIII

問題

• グローバル変数を使用

class Solution 
{
private:
    vector<vector<int>> res;
    vector<int> path;
    void backtracing(int target_sum, int k, int sum,  int start_index)
    {
        if (sum > target_sum)
        {
            return;
        }
        if (path.size() == k)
        {
            if (sum == target_sum)
            {
                res.push_back(path);
            }
            return;
        }
        for (int i = start_index; i <= 9 -( k - path.size()) + 1; i++)
        {
            path.push_back(i);
            sum += i;
            backtracing(target_sum, k, sum, i + 1);
            sum -= i;
            path.pop_back();
        }

    }
public:
    vector<vector<int>> combinationSum3(int k, int n) 
    {
        backtracing(n, k, 0, 1);
        return res;

    }
};

• 引数を通じて値を渡す

class Solution {
public:
    void backtracing(int start_index, int k ,int n, int sum, vector<vector<int>>& res, vector<int>& vec)
    {
        if (sum > n)
        {
            return;
        }
        if (vec.size() == k)
        {
            if (sum == n)
            {
                res.push_back(vec);
            }
            return;

        }
        for (int i = start_index;  i <= 9 -( k - vec.size()) + 1; i++)
        {
            vec.push_back(i);
            sum += i;
            backtracing(i + 1, k, n, sum, res, vec);
            vec.pop_back();
            sum -= i;
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) 
    {
        vector<vector<int>> res;
        vector<int> vec;
        backtracing(1, k, n, 0, res, vec);

        return res;
    }
};

電話番号の文字列の組み合わせ

問題

class Solution {
private:
    const string letterMap[10] = {
        "", // 0
        "", // 1
        "abc", // 2
        "def", // 3
        "ghi", // 4
        "jkl", // 5
        "mno", // 6
        "pqrs", // 7
        "tuv", // 8
        "wxyz", // 9
    };
public:
    vector<string> result;
    string s;
    void backtracking(const string& digits, int index) {
        if (index == digits.size()) {
            result.push_back(s);
            return;
        }
        int digit = digits[index] - '0';        // indexの数字をintに変換
        string letters = letterMap[digit];      // 数字に対応する文字列を取得
        for (int i = 0; i < letters.size(); i++) {
            s.push_back(letters[i]);            // 処理
            backtracking(digits, index + 1);    // 再帰呼び出し
            s.pop_back();                       // 戻す
        }
    }
    vector<string> letterCombinations(string digits) {
        s.clear();
        result.clear();
        if (digits.size() == 0) {
            return result;
        }
        backtracking(digits, 0);
        return result;
    }
};

私の解答

class Solution {
public:
    unordered_map<char, string> mp = {
    {'2', "abc"},
    {'3', "def"},
    {'4', "ghi"},
    {'5', "jkl"},
    {'6', "mno"},
    {'7', "pqrs"},
    {'8', "tuv"},
    {'9', "wxyz"}
};

    void backtracing(int start_index, string digits, string& s, vector<string>& res)
    {
        if (s.size() == digits.size())
        {
            res.push_back(s);
            return;
        }
        for(int i = start_index; i < digits.size(); i++)
        {
            char a = digits[i];
            for(int j = 0; j < mp[a].size(); j++)
            {
                s.push_back(mp[a][j]);
                backtracing(i + 1, digits, s, res);
                s.pop_back();
            }
        }

    }
    vector<string> letterCombinations(string digits) 
    {
        vector<string> res;
        string s;
        if (digits.size() == 0)
        {
            return res;

        }
        backtracing(0, digits, s, res);
        return res;
    }
};

和が指定された組み合わせ

問題 私の解答

class Solution {
public:
    void backtracing(int start_index, vector<int>& candidates, int target, int &sum, vector<vector<int>> &res, vector<int> &vec)
    {
        if (sum > target)
        {
            return;
        }
        if (sum == target)
        {
        res.push_back(vec);
        }
        for(int i = start_index; i < candidates.size(); i++)
        {
            vec.push_back(candidates[i]);
            sum += candidates[i];
            backtracing(i, candidates, target, sum, res, vec);
            // 戻す
            sum -= candidates[i];
            vec.pop_back();
        }

    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) 
    {
        vector<vector<int>> res;
        vector<int> vec;
        if (candidates.size() == 0)
        {
            return res;
        }
        int sum = 0;

        backtracing(0, candidates, target, sum, res, vec);
        return res;
    
    }
};

注意点：vec.push_back(candidates[i]) ，sum += candidates[i] 剪定最適化

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
        if (sum == target) {
            result.push_back(path);
            return;
        }

        // sum + candidates[i] > target なら探索を停止
        for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
            sum += candidates[i];
            path.push_back(candidates[i]);
            backtracking(candidates, target, sum, i);
            sum -= candidates[i];
            path.pop_back();

        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        result.clear();
        path.clear();
        sort(candidates.begin(), candidates.end()); // ソートが必要
        backtracking(candidates, target, 0, 0);
        return result;
    }
};

和が指定された組み合わせII（*）

問題

class Solution {
public:
    void backtracing(vector<int>& candidates, int target, int start_index, int& sum, vector<vector<int>>& res, vector<int>& vec)
    {
        if (sum > target)
        {
            return;
        }
        if (sum == target)
        {
            res.push_back(vec);
            return;
        }
        for(int i = start_index; i < candidates.size() && sum + candidates[i] <= target; i++)
        {
            // 重複要素をスキップ
            if (i > start_index && candidates[i] == candidates[i - 1])
            {
                continue;
            }
            vec.push_back(candidates[i]);
            sum += candidates[i];
            backtracing(candidates, target, i + 1, sum, res, vec);
            // 戻す
            sum -= candidates[i];
            vec.pop_back();
        
        }

    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) 
    {
        vector<vector<int>> res;
        vector<int> vec;
        if (candidates.size() == 0)
        {
            return res;
        }
        // ソート
        sort(candidates.begin(), candidates.end());

        int sum = 0;
        backtracing(candidates, target, 0, sum, res, vec);

        return res;
    }
};

重複要素のスキップ処理：

            // 重複要素をスキップ
            if (i > start_index && candidates[i] == candidates[i - 1])
            {
                continue;
            }

回文分割（*）

問題

class Solution {
private:
    vector<vector<string>> res;
    vector<string> path; // 回文の部分文字列
    vector<vector<bool>> is_palindrome; // 事前に計算した回文判定結果
    void backtracing(const string& s, int start_index)
    {
        if (start_index >= s.size()) // 文字列末尾に到達
        {
            res.push_back(path);
            return;
        }
        for(int i = start_index;i < s.size(); i++)
        {
            if(is_palindrome[start_index][i]) // 回文である場合
            {
                string str = s.substr(start_index, i - start_index + 1);
                path.push_back(str);
            }
            else // 回文ではない場合
            {
                continue;
            }
            backtracing(s, i + 1); // 次の部分文字列を検索
            // 戻す
            path.pop_back();
        }

    }

    void compute_palindrome(const string& s)
    {
         // isPalindrome[i][j] は s[i:j] が回文かどうかを示す
        is_palindrome.resize(s.size(), vector<bool>(s.size(), false));
        for(int i = s.size() - 1; i >= 0 ; i--) // 後ろから計算
        {
            for(int j = i; j < s.size(); j++)
            {
                if (j == i)
                {
                    is_palindrome[i][j] = true;
                }
                else if(j - i == 1)
                {
                    is_palindrome[i][j] = (s[i] == s[j]);
                }
                else
                {
                    is_palindrome[i][j] = (s[i] == s[j] && is_palindrome[i+1][j-1]);
                }
            }
        }
    }

public:
    vector<vector<string>> partition(string s) 
    {
        res.clear();
        path.clear();
        compute_palindrome(s);
        backtracing(s, 0);
        return res;
    }
};

IPアドレスの修復

問題

class Solution {
public:
    bool isvalidadd(string s)
    {
        // 先頭に0があるかチェック
        if (s.size() > 1 && s[0] == '0') 
        {
            return false;
        }
        int add = stoi(s);
        if (add >= 0 && add <= 255)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    void backtracing(string s, vector<string>& tmp, vector<string>& res, int start_index)
    {
        
        if (tmp.size() == 4) // 4つのセグメントが完成
        {
            if (start_index == s.size()) // すべての文字が使用された場合
            {
                string ip = tmp[0] + "." + tmp[1] + "." + tmp[2] + "." + tmp[3];
                res.push_back(ip);
            }
            return;
        }

        for(int i = start_index; i < start_index + 3 && i < s.size(); i++)
        {
            string sub = s.substr(start_index, i - start_index + 1);
            if (isvalidadd(sub))
            {
                tmp.push_back(sub);    
                backtracing(s, tmp, res, i + 1);
                tmp.pop_back();     
            }

        }
    }
    vector<string> restoreIpAddresses(string s) 
    {
        vector<string> res;
        vector<string> tmp;
        backtracing(s, tmp, res, 0);

        return res;
    }
};

部分集合

問題

class Solution {
public:
    void backtracing(vector<vector<int>>& res, vector<int>& path, int start_index, vector<int>& nums)
    {
        res.push_back(path);
        if (start_index >= nums.size())
        {
            return;
        }
        for(int i = start_index; i < nums.size(); i++)
        {
            path.push_back(nums[i]);
            backtracing(res, path, i + 1, nums);
            path.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) 
    {
        vector<vector<int>> res;
        vector<int> path;
        backtracing(res, path, 0, nums);

        return res;
    }
};

重複を含む部分集合（*）

問題

class Solution {
public:
    void backtracing(vector<vector<int>>& res, vector<int>& path,  vector<bool>& used, vector<int>& nums, int start_index)
    {
        res.push_back(path);
        if (start_index >= nums.size())
        {
            return;
        }
        for(int i = start_index; i < nums.size(); i++)
        {
            // used[i-1] == true: 同じ枝で使われた要素
            // used[i-1] == false: 同じ層で使われた要素
            // 同じ層の要素をスキップ
            if (i > 0 && nums[i-1] == nums[i] && used[i-1] == false)
            {
                continue;
            }
            path.push_back(nums[i]);
            used[i] = true;
            backtracing(res, path, used, nums, i + 1);
            used[i] = false;
            path.pop_back();


        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) 
    {
        vector<vector<int>> res;
        vector<int> path;
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end()); // 重複を避けるためにソート
        backtracing(res, path, used, nums, 0);

        return res;
    }
};

非減少の部分列（*）

問題

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void backtracing(vector<int>& nums, int start_index)
    {
        if (path.size() > 1)
        {
            res.push_back(path);
            // 葉ノード以外にも追加
        }
        unordered_set<int> uset; // 同一層の要素を重複させない
        for(int i = start_index; i < nums.size(); i++)
        {
            if ((!path.empty() && nums[i] < path.back()) || uset.find(nums[i]) != uset.end())
            {
                continue;
            }
            uset.insert(nums[i]); // この層で使用した要素を記録
            path.push_back(nums[i]);
            backtracing(nums, i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) 
    {
        res.clear();
        path.clear();
        backtracing(nums, 0);
        return res;
    }
};

全順列

問題 順列問題ではstart_indexではなくused配列を使って要素の使用状況を管理します。 各レベルは0から開始して探索します。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void backtracing(vector<int>& nums, vector<bool>& used)
    {

        if (path.size() == nums.size())
        {
            res.push_back(path);
            return;
        }
        for(int i = 0; i < nums.size(); i++)
        {
            if (used[i] == true) // 使用済みの要素はスキップ
            {
                continue; 
            }
            path.push_back(nums[i]);
            used[i] = true;
            backtracing(nums, used);
            // 戻す
            used[i] = false;
            path.pop_back();
        }      

    }
    vector<vector<int>> permute(vector<int>& nums) 
    {
        res.clear();
        path.clear();
        vector<bool> used(nums.size(), false);
        backtracing(nums, used);
        return res;
    }
};

注意：

    if (used[i] == true) // 使用済みの要素はスキップ
    {
        continue; 
    }

重複を含む順列（*）

問題

重複を避けるためには事前に要素をソートする必要があります。 同じ層では同じ要素を2回使用しないようにします。 同じ枝では同じ要素を複数回使用できます。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void backtracing(vector<int>& nums, vector<bool>& used)
    {
        if (path.size() == nums.size())
        {
            res.push_back(path);
            return;
        }
        for(int i = 0; i < nums.size(); i++)
        {
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) // 同じ枝での重複を避ける
            {
                continue;
            }
            if (used[i] == false)
            {
                used[i] = true;
                path.push_back(nums[i]);
                backtracing(nums, used);
                path.pop_back();
                used[i] = false;
            }

        }

    }
    vector<vector<int>> permuteUnique(vector<int>& nums) 
    {
        res.clear();
        path.clear();
        // 重複を避けるためには事前にソート
        sort(nums.begin(), nums.end());
        vector<bool> used(nums.size(), false);
        backtracing(nums, used);
        return res;
    }
};

行程の再配置（*）

問題

class Solution {
private:
//unordered_map<出発地, map<到着地, 航班回数>> targets
    unordered_map<string, map<string, int>> targets;
    bool backtracing(int ticket_num, vector<string>& res)
    {
        if (res.size() == ticket_num + 1)
        {
            return true; // 結果は一つだけ
        }
        for(pair<const string, int>& target : targets[res[res.size() - 1]])
        {
            if (target.second > 0) // 航班があるか
            {
                res.push_back(target.first);
                target.second--;
                if (backtracing(ticket_num, res))
                {
                    return true;
                }
                res.pop_back();
                target.second++;
            }
        }
        return false;
    }
public:
    vector<string> findItinerary(vector<vector<string>>& tickets) 
    {
        targets.clear();
        vector<string> res;
        for(const vector<string>& vec : tickets)
        {
            targets[vec[0]][vec[1]]++; // マッピングを記録
        }
        res.push_back("JFK"); // 出発地
        backtracing(tickets.size(), res);
        return res;
    }
};

N皇后（*）

問題

盤面の幅はforループの回数、深さは盤面の高さに対応します。

class Solution {
private:
    bool isvlaid(int row, int col, vector<string>& chessboard, int n)
    {
        // 列のチェック
        for(int i = 0; i < row; i++)
        {
            if(chessboard[i][col] == 'Q')
            {
                return false;
            }
        }
        // 45度方向のチェック
        for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--)
        {
            if (chessboard[i][j] == 'Q')
            {
                return false;
            }
        }
        // 135度方向のチェック
        for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++)
        {
            if (chessboard[i][j] == 'Q')
            {
                return false;
            }
        }
        return true;
    } 
    vector<vector<string>> res;
    // n: 盤面の大きさ
    // row: 現在の行
    void backtracing(int n, int row, vector<string>& chessboard)
    {
        if (row == n)
        {
            res.push_back(chessboard);
            return;
        }
        for(int col = 0; col < n; col++)
        {
            if (isvlaid(row, col, chessboard, n)) // 合法性を確認
            {
                chessboard[row][col] = 'Q';
                backtracing(n, row + 1, chessboard);
                chessboard[row][col] = '.';// 戻す
            }
        }
    }
public:

    vector<vector<string>> solveNQueens(int n) 
    {
        res.clear();
        vector<string> chessboard(n, string(n, '.'));
        backtracing(n, 0, chessboard);
        return res;
    }
};

数独の解法

問題 二次元再帰問題

class Solution {
private:
    bool isvalid(int row, int col, char val, vector<vector<char>>& board)
    {
        for(int i = 0; i < 9; i++)
        {
            if (board[row][i] == val) // 行の重複チェック
            {
                return false;
            }
        }
        for(int j = 0; j < 9; j++) // 列の重複チェック
        {
            if (board[j][col] == val)
            {
                return false;
            }
        }
        int start_row = (row / 3) * 3;
        int start_col = (col / 3) * 3;
        for(int i = start_row; i < start_row + 3; i++) // 3x3領域の重複チェック
        {
            for(int j = start_col; j < start_col + 3; j++)
            {
                if (board[i][j] == val)
                {
                    return false;
                }
            }

        }
        return true;
    }
    bool backtracing(vector<vector<char>>& board)
    {
        for(int i = 0; i < board.size(); i++)
        {
            for(int j = 0; j < board[0].size(); j++)
            {
                if (board[i][j] == '.')
                {
                    for (char k = '1'; k <= '9'; k++) // (i,j)にkを入れられるか
                    {
                        if (isvalid(i, j, k, board))
                        {
                            board[i][j] = k;
                            if (backtracing(board)) return true;// 見つけたら即時終了
                            board[i][j] = '.';// 戻す
                        }
                    }
                    return false; // 9つの数字を試してもだめなら失敗
                }
            }
        }
        return true; // すべての空きマスを埋めた場合
    }
public:
    void solveSudoku(vector<vector<char>>& board) 
    {
        backtracing(board);
    }
};