leetcode 46. 全排列

思路

深度优先遍历:回溯,递归(终止条件:选择的当前数字数量等于原始数组的大小)

leetcode 46. 全排列

状态变量
1.递归到第几层,depth
2.已经选择了哪些数Path
3.布尔数组 used
非叶子节点选择分枝

代码:

class Solution {
public:
    void backtrack(vector<vector<int>>&res,vector<int>&output,int first,int len)
    {
        if (first == len)//递归出口  所有数都填完了
        {
            res.emplace_back(output);
            //return; //什么操作都不做
        }
        //循环
        for(int i = first;i<len;++i)
        {
            //维护动态数组
            swap(output[i],output[first]);
            //继续递归填下一个数
            backtrack(res,output,first+1,len);
            //撤销操作
            swap(output[i],output[first]); //撤销交换  回退到上一个分支
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>>res;
        backtrack(res,nums,0,(int)nums.size());
        return res;
    }
};

调用STL的结果

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>>result;
        sort(nums.begin(),nums.end());
        do{
            result.push_back(nums);
        }while(next_permutation(nums.begin(),nums.end()));
       return  result;
    }
};

 

上一篇:46 级 ——阅读题


下一篇:etcd查看leader节点