力扣-全排列II & 重新安排行程

47. 全排列 II

class Solution {
public:
    vector<int> path;//单一序列
    vector< vector<int>> ans;//序列集合
    bool isUsed[8] = {false};//回溯一整根树枝时需要判断某个位置的数字是否使用过
    //回溯三部曲
    //1.确认回溯返回类型，返回参数,因为是要所有的排列组合，所以不需要记录startIndex
    void backtracing(vector<int>& nums)
    {
        //2.终止条件
        if(path.size() == nums.size())
        {
            ans.emplace_back(path);
            return;
        }
        //3.每次回溯的遍历过程，去重只要在每次回溯的循环中，不出现相同的数字即可
        //起初每个数字都没用过
        bool isRepeat[21] = {false};
        for(int i = 0; i < nums.size(); i++)
        {
            //如果这一位的数字使用过，继续
            if(isUsed[i]) continue;
            //如果在同一树层（也就是一次回溯的循环中，出现了相同的数字，也要继续）
            if(isRepeat[nums[i] + 10]) continue;
            //如果没用过，而且是首次出现
            isRepeat[nums[i] + 10] = true;//设置为true，这样的话，下次再出现就跳过了
            isUsed[i] = true;//设置为true，用过就跳过了
            path.emplace_back(nums[i]);
            backtracing(nums);
            path.pop_back();
            isUsed[i] = false;//当这个节点回溯完了，要将是否使用过重置为false
        }

    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        backtracing(nums);
        return ans;
    }
};

    这次不仅要在全局判断是否使用过，还要判断是否重复使用过（为了去重）

332. 重新安排行程

class Solution {
public:

    //unordered_map<出发机场， <目标机场，航班次数>>
    unordered_map<string, map<string, int>> targets;
    //储存行程
    vector<string> result;
    //机票的张数
    int ticketsNum;
    //回溯三部曲
    //1.确认返回类型，参数
    bool backtracing(string cur)
    {
        //2.中止条件,当行程中的机场数量等于及票数+1时
        if(result.size() == ticketsNum + 1)
        {
            return true;
        }
        //3.每次回溯的遍历,遍历当前机场所有的目标机场
        for(const pair<string, int> & target : targets[cur])
        {
            //如果目标机场已经飞过，没有航班次数了
            if(target.second == 0) continue;
            else//如果没有飞过
            {
                //把这个没飞过的机场加入到result中
                result.emplace_back(target.first);
                //航班次数-1，说明这次用掉了一张机票,机票出发机场为cur，目标机场为target.first
                targets[cur][target.first]--;
                //如果在某次回溯中返回了true，
                //说明一直有满足条件的机场，最终result的长度也=ticketsNum + 1了
                //那么直接退出递归
                if(backtracing(target.first)) return true;
                //说明这条行程不行，航班次数加回来，去飞下一个机场
                targets[cur][target.first]++;
                result.pop_back();//删掉
            }
        }
        //如果遍历完了，还没有结束，那么说明这条行程不对
        return false;
    }
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        //初始化出发机场到目标机场的哈希表
        //遍历每一张机票
        for(vector<string> & ticket : tickets)
        {
            //ticket[0]指的是机票的出发机场，ticket[1]是目标机场，++就是航班次数+1
            targets[ticket[0]][ticket[1]]++;
        }
        //从JFK出发
        result.emplace_back("JFK");
        ticketsNum = tickets.size();
        backtracing("JFK");
        return result;
    }
};

1. 行程要字典排序最小的那个，所以这里要用哈希表map来存机票，出发机场可能有多个目标机场，到目标机场的机票通过map自动排好序，那么再遍历的时候，自然是从字典顺序最小的开始

2. 行程要避免死循环，所以1中的map的第二个值是航班次数，一旦用过了，就要减掉，这样之后再回溯的时候发现航班次数为0了就会跳过

3. 判断中止条件，就是当找到第一条行程时，他就是答案了，因为按1中的逻辑，他已经是字典序最小的行程了，这个时候返回true，那么在之前的回溯也会返回true，一层一层返回回去，就直接结束递归了

4. 遍历机场所有机场的时候，使用const pair<string, int>来遍历出发机场也就是cur的unordered_map中的第二个参数map