leetcode 46. 全排列-回溯算法

解题思路

• 本题输出所有可能的排列，采用回溯算法

• 注意：

  1.筛选条件

方案一:

//选择unordered_map进行重复筛选
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int>path;
        vector<vector<int>>res;
        unordered_set<int>myset;//存储path中的元素，避免重复
        backtrace(nums,res,path,myset);

        return res;
    }
    void backtrace(const vector<int>& nums,vector<vector<int>>& res,vector<int>& path,unordered_set<int>&myset){
        if(path.size() == nums.size()){
            res.push_back(path);
            return;
        }
        for(int i = 0;i<nums.size();++i){
            // 进行筛选
            if(!myset.count(nums[i])){
                myset.insert(nums[i]);
                path.push_back(nums[i]);
                backtrace(nums,res,path,myset);
                myset.erase(nums[i]);
                path.pop_back();
            }
            
        }
    }
    
};
           

方案二:

//选择vector进行去重筛选
class Solution {
private:
    vector<int>record;//记录path中被插入元素在nums中的下标，避免在一次path中重复使用同一个下标元素
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int>path;
        vector<vector<int>>res;
        record.resize(nums.size());
        backtrace(nums,res,path,record);

        return res;
    }
    void backtrace(const vector<int>& nums,vector<vector<int>>& res,vector<int>& path,vector<int>&record){
        if(path.size() == nums.size()){
            res.push_back(path);
            return;
        }
        for(int i = 0;i<nums.size();++i){
            // 进行筛选
            if(!record[i]){
                record[i] = 1;
                path.push_back(nums[i]);
                backtrace(nums,res,path,record);
                record[i] = 0;
                path.pop_back();
            }
            
        }
    }
    
};