代码随想录算法训练营Day30 | 332.重新安排行程 51. N皇后 37. 解数独 总结

代码随想录算法训练营Day30 | 332.重新安排行程 51. N皇后 37. 解数独 总结

回溯总结

回溯解决的问题：

组合问题：N个数里面按一定规则找出k个数的集合
排列问题：N个数按一定规则全排列，有几种排列方式
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
棋盘问题：N皇后，解数独等等

回溯模板

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

LeetCode 332.重新安排行程

题目链接：LeetCode 332.重新安排行程

思路：

1. 用targets存放起点，终点以及次数
2. 依次遍历res的末尾元素的下一个节点

class Solution {
public:

    unordered_map<string, map<string, int>> targets;

    bool backtracking(int ticket_num, vector<string>& res){
        if(ticket_num+1==res.size()) 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(backtracking(ticket_num, res)) return true;
                target.second++;
                res.pop_back();
            }
        }
        return false;
    }
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        targets.clear();
        vector<string> res;
        for(vector<string> vec:tickets){
            targets[vec[0]][vec[1]]++;
        }
        res.push_back("JFK");
        backtracking(tickets.size(), res);
        return res;
    }
};

注意 ：

1. backtracking return的值用于判断是否结束回溯

LeetCode 51. N皇后

题目链接：LeetCode 51. N皇后

思路：

注意 ：
1.
2.
3.
4.

LeetCode 37. 解数独

题目链接：LeetCode 37. 解数独

思路：

注意 ：
1.
2.
3.
4.