【算法】回溯法

算法思想

回溯(Backtrack)是一种搜索方法，常用于排列问题、搜索问题的求解。其基本思想为DFS(Depth-First Search)：分步求解，步步为营，一旦探索完该状态的所有可能性，就回退到前一个状态。

回溯算法的模板大概如下:

class Solution {
public:
    void Backtrack(vector<T>& record, vector<T>& temp, vector<T> choices...) {
        if IsTerminate(temp) {
            record.push_back(temp);
            return;
        }
        
        for(T choice : choices) {
            if(IsLegal(choice)) {
                temp.push_back(choice);
                Backtrack(record, temp, choices);
                temp.pop_back(choice);
            }
        }
    }
    vector<T> Solve(vector<T> choices) {
        vector<T> record;ge shu
        vector<T> temp;
        ...
        Backtrack(record, temp, choices, ...);
        return record;
    }
};

回溯函数里，首先判断是否为终止状态，若是，则将临时状态加入最终结果，若否，则遍历所有的可行选择，加入临时状态，接着继续回溯，等待回溯完成，将选择从临时状态中删除。

实战

回溯可以应用于排列问题，比如说Leetcode 46. Permutations：

class Solution {
public:
    void backtrack(vector<int>& curr, vector<vector<int>>& answ, vector<int>& nums) {
        if(curr.size() == nums.size()) {
            answ.push_back(curr);
            return;
        }

        for(int num : nums) {
            if(find(curr.begin(), curr.end(), num) == curr.end()) {
                curr.push_back(num);
                backtrack(curr, answ, nums);
                curr.pop_back();
            }
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> curr;
        backtrack(curr, result, nums);
        return result;
    }
};

回溯函数中，先判断是否为一个可行的全排列，若是，则将其加入结果列表，否则就挑选合适的数字加入临时状态，挑选的判据为该数字是否已经出现过。

也可以应用于搜索问题上，比如Leetcode 797. All Paths From Source to Target:

class Solution {
public:
    void backtrack(vector<vector<int>>& result, vector<vector<int>>& graph, int curr_node, vector<int>& curr_vec) {
        if(curr_node == graph.size() - 1) {
            result.push_back(curr_vec);
        }

        for(int node : graph[curr_node]) {
            if(find(curr_vec.begin(), curr_vec.end(), node) == curr_vec.end()) {
                curr_vec.push_back(node);
                backtrack(result, graph, node, curr_vec);
                curr_vec.pop_back();
            }
        }
    }
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<vector<int>> result;
        vector<int> temp_vec;
        temp_vec.push_back(0);
        backtrack(result, graph, 0, temp_vec);
        return result;
    }
};

回溯也可以变得很复杂，比如有Leetcode 22. Generate Parentheses：

class Solution {
public:
    // ( - +1 ) - -1
    void Backtrack(vector<string>& result, int n, string& curr, int l_num, int r_num) {
        if(curr.size() == 2 * n) {
            result.push_back(curr);
            return;
        }
        if(l_num == r_num) {
            curr += '(';
            Backtrack(result, n, curr, l_num+1, r_num);
            curr = curr.substr(0, curr.size() - 1);
        } else if(l_num == n) {
            curr += ')';
            Backtrack(result, n, curr, l_num, r_num+1);
            curr = curr.substr(0, curr.size() - 1);
        } else if(l_num < n) {
            if(l_num == r_num) {
                curr += '(';
                Backtrack(result, n, curr, l_num+1, r_num);
                curr = curr.substr(0, curr.size() - 1);
            } else {
                curr += '(';
                Backtrack(result, n, curr, l_num+1, r_num);
                curr = curr.substr(0, curr.size() - 1);
                curr += ')';
                Backtrack(result, n, curr, l_num, r_num+1);
                curr = curr.substr(0, curr.size() - 1);
            }
        }
    }
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        string now = "";
        Backtrack(result, n, now, 0, 0);
        return result;
    }
};

生成括号时，合法性判据为已经生成的左右括号个数。