46. 全排列

给定一个 没有重复 数字的序列，返回其所有可能的全排列。 示例:

输入：[1,2,3] 输出：[ [1,2,3], [1,3,2], [2,1,3],[2,3,1],[3,1,2],[3,2,1] ]

解题思路

代码实现

class Solution {
public:
    vector<int> sortNums;//原始序列的排序
    vector<vector<int>> res;//存储最后结果
    vector<int> solveOne;//一个全排列
    vector<int> used;//标记位置i的元素是否被使用过
    int len;
    vector<vector<int>> permute(vector<int>& nums) {
        len = nums.size();
        sortNums = nums;
        sort(sortNums.begin(),sortNums.end());//排序与否不影响最后结果
        for(int i = 0;i < len;i++) used.push_back(false);
        recurDep();
        return res;
    }
    void recurDep(){
        if(solveOne.size() == len){
            res.push_back(solveOne);
            return;
        }
        for(int i = 0;i < len;i++) {
            if(!used[i]){
                solveOne.push_back(sortNums[i]);
                used[i] = true;//标记为已经使用过了
                recurDep();//往下一层递归
                //撤销选择，回退
                solveOne.pop_back();
                used[i] = false;
            }
        }
    }    
};