代码随想录算法训练营第二十五天| 332.重新安排行程（可跳过） 51. N皇后（可跳过） 37. 解数独（可跳过）

 1 //机票信息 -》 一条遍历所有机场的路径
 2 //步骤：
 3 // 1，根据 start 压进去它的所有目的地信息
 4 // 2， 目的地作为起始节点，进行遍历
 5 // 3，如果这条路径到最后也没有遍历所有，那么就回复原装，开始遍历下一条路径
 6 bool findItinerary_trackBack(map<string,map<string,int>>&tickets,int ticketNum, string start, vector<string>&result)
 7 {
 8     if (result.size() == ticketNum +1)
 9     {
10         return true;
11     }
12 
13     for (pair<const string,int>& ticket : tickets[start])
14     {
15         if (ticket.second > 0)
16         {
17             result.push_back(ticket.first);
18             ticket.second--;
19             bool isComplete = findItinerary_trackBack(tickets, ticketNum, ticket.first, result);
20             if (isComplete) return true;
21             ticket.second++;
22             result.pop_back();
23         }
24 
25     }
26     return false;
27 }
28 
29 vector<string> findItinerary(vector<vector<string>>& tickets) {
30     //需要tickets，转换成map《start,map》
31     map<string, map<string, int>> tickets_map;
32     for (auto ticket : tickets)
33     {
34         
35         tickets_map[ticket[0]][ticket[1]]++;
36     }
37 
38     vector<string>result;
39     result.push_back("JFK");
40     findItinerary_trackBack(tickets_map, tickets.size(), "JFK", result);
41     return result;
42 }