78.子集

画图分析：

 思路：横向遍历，每次遍历的时候都进行一次添加，然后进行纵向递归，递归完之后进行回溯。

• 注意：空集也是子集。

90.子集||

分析：和上题一样，区别在于有重复数字

思路：组合问题有重复都考虑先排序再操作！

class Solution {
public:
    vector<vector<int>>res;
    vector<int>mid;
    void backtrace(vector<int>&nums,int start){
        if(find(res.begin(),res.end(),mid)==res.end())//去重
            res.push_back(mid);
        if(start==nums.size())
            return;
        
        for(int i=start;i<nums.size();i++){
            
            mid.push_back(nums[i]);
            backtrace(nums,i+1);
            mid.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(),nums.end());//需要排序
        backtrace(nums,0);
        return res;
    }
};

491.递增子序列

class Solution {
public:
    vector<vector<int>>midRes,res;
    vector<int>mid;
    void backtrace(vector<int>&nums,int start){
        if(mid.size()>=2 ){//条件限制
            midRes.push_back(mid);
        }
        if(start==nums.size())//终止条件
            return;
        unordered_set<int> vistedSet;
        for(int i=start;i<nums.size();i++){
            if(vistedSet.find(nums[i])!=vistedSet.end())//去重
                continue;
            if(!mid.empty() && mid.back()>nums[i])//递增条件
                continue;
            //judge[nums[i]]=true;
            vistedSet.insert(nums[i]);//遍历标记
            mid.push_back(nums[i]);
            backtrace(nums,i+1);
            mid.pop_back();//回溯
        }
    }
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backtrace(nums,0);
        return midRes;
    }
};

46.全排列

思路：跟子集的代码几乎一样，主要区别在于

• 每次遍历都从0开始，并且做树枝去重

class Solution {
public:
    vector<vector<int>>res;
    vector<int>mid;
    void backtrace(vector<int>&nums,int start){
        if(start==nums.size()){
            res.push_back(mid);
        }
        for(int i=0;i<nums.size();i++){
            if(find(mid.begin(),mid.end(),nums[i])!=mid.end())//树枝去重
                continue;
            mid.push_back(nums[i]);
            backtrace(nums,start+1);
            mid.pop_back();
        }
    }
    //树枝去重
    vector<vector<int>> permute(vector<int>& nums) {
        backtrace(nums,0);
        return res;
    }
};

47.全排列||

思路一：使用哈希表进行树枝下标去重（因为有重复元素）

问题：在数组去重时时间复杂度过高

class Solution {
public:
    vector<vector<int>>res;
    vector<int>mid;
    unordered_map<int,bool>map;
    void backtrace(vector<int>&nums,int start){
        if(start==nums.size()){
            if(find(res.begin(),res.end(),mid)==res.end())//数组去重
                res.push_back(mid);
            return;
        }

        for(int i=0;i<nums.size();i++){
            if(map[i])//树枝去重
                continue;
            mid.push_back(nums[i]);
            map[i]=true;
            backtrace(nums,start+1);
            mid.pop_back();
            map[i]=false;
        }
    }
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        //sort(nums.begin(),nums.end());
        backtrace(nums,0);
        return res;
    }
};

323.重新安排行程 

思路：首先记录航班的映射关系，然后从起点开始根据映射关系一一添加（横向遍历，纵向递归）

注意：

• 起点航班要先添加

• 如果添加的路线等于航班数+1时，说明已经走完全部航班（如五个航班，必然是六个站点）

• 递归深入的时候需要判断当前映射关系是否被添加过

class Solution {
public:
    unordered_map<string,map<string,int>>targets;
    vector<string>midres;
    bool backtrace(vector<vector<string>>& tickets){
        if(midres.size()==tickets.size()+1)//航班已经走完的终止条件
            return true;
        
        for(pair<const string,int>&target:targets[midres[midres.size()-1]]){//遍历映射关系
            if(target.second>0){//当映射关系还存在时
                midres.push_back(target.first);
                target.second--;
                if(backtrace(tickets)) return true;//已经找到一条路线
                midres.pop_back();
                target.second++;
            }
        }
        return false;
    }
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        midres.push_back("JFK");//先添加起点航班
        for(auto it:tickets)
            targets[it[0]][it[1]]++;//记录映射关系
        backtrace(tickets);
        return midres;
    }
};