给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。

提示：

1. 如果存在多种有效的行程，请你按字符自然排序返回最小的行程组合。例如，行程 [“JFK”, “LGA”] 与 [“JFK”, “LGB”] 相比就更小，排序更靠前
2. 所有的机场都用三个大写字母表示（机场代码）。
3. 假定所有机票至少存在一种合理的行程。
4. 所有的机票必须都用一次 且 只能用一次。

示例 1：

输入：[["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
输出：["JFK", "MUC", "LHR", "SFO", "SJC"]

示例 2：

输入：[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。

Solution

参考 代码随想录

• 回溯法

需要解决的问题：

1. 一个行程中，如果航班处理不好容易变成一个圈，成为死循环
2. 有多种解法，字母序靠前排在前面，如何该记录映射关系呢 ？
3. 使用回溯法（也可以说深搜） 的话，那么终止条件是什么呢？
4. 搜索的过程中，如何遍历一个机场所对应的所有机场。

在遍历 unordered_map<出发机场, map<到达机场, 航班次数>> targets的过程中，「可以使用”航班次数”这个字段的数字做相应的增减，来标记到达机场是否使用过了。」

// @lc code=start
class Solution {
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"); // 起始机场
        backtrack(tickets.size(), res);
        return res;
    }
private:
    // unordered_map<出发机场, map<到达机场, 航班次数>> targets
    unordered_map<string, map<string, int>> targets;

    bool backtrack(int ticketNum, vector<string>& res) {
        // 经过的机场个数 = 机票数 + 1
        if (res.size() == ticketNum + 1) return true;

        string cur = res[res.size() - 1];  // 目前所在的机场
        for (pair<const string, int>& target : targets[cur]) {
            if (target.second > 0) {
                // 记录是否还能到达该机场
                res.push_back(target.first);
                target.second--;
                if (backtrack(ticketNum, res)) return true;
                res.pop_back();
                target.second++;
            }
        }
        return false;
    }
};
// @lc code=end