leetcode 46. 全排列

佚名 6年前 (2019-04-12) 随笔 1131人围观抢沙发百度已收录

很经典很经典，虽然AC高但难度不小

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

采用深度优先搜索的代码：

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> temp,visited(nums.size(),0);
        sort(nums.begin(),nums.end());
        DFS(nums,0,visited,temp,res);
        return res;
    }
    void DFS(vector<int>& nums,int index,vector<int>& visited,vector<int>& temp,vector<vector<int>>& res){
        //递归边界，当一个排列的数达到n个后，即形成了一个排列
        if(index==nums.size()){res.push_back(temp);return;}
        //递归形式:输出以nums[i]为第一个数的所有排列，
        for(int i=0;i<nums.size();i++){
            if(visited[i]==0){
                temp.push_back(nums[i]);
                visited[i]=1;
                //递归调用时，输出前（index+1）个数确定的所有排列
                DFS(nums,index+1,visited,temp,res);
                //递归调用时，前（index+1）个数确定的所有排列输出完成，将后面所用到的元素visited设为0，并将temp中第（index+1）个数删除，然后按顺序继续加入下一个没有被添加到temp中的数
                temp.pop_back();
                visited[i]=0;
            }
        }
    }
};