题目

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

分析

思路是递归。通过去掉nums中的一个数，然后对于剩下的数进行排列得到tmp。对于tmp中的每个结果，再在末尾插入之前去掉的数字即可。另外递归的出口为，当nums中只有一个数时，直接返回包含该数的结果。

实现

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<bool> used(nums.size(), false);
        vector<vector<int>> ans=solve(nums, used, nums.size());
        for(int i=0; i<ans.size(); i++){
            reverse(ans[i].begin(), ans[i].end());
        }
        return ans;
    }
private:
    vector<vector<int>> solve(vector<int>& nums, vector<bool> &used, int n){
        vector<vector<int>> ans;
        if(n==1){
            for(int i=0; i<nums.size(); i++){
                if(used[i]) continue;
                ans.push_back({nums[i]});
            }
            return ans;
        }
        for(int i=0; i<nums.size(); i++){
            if(used[i]) continue;
            used[i] = true;
            vector<vector<int>> tmp=solve(nums, used, n-1);
            for(int j=0; j<tmp.size(); j++){
                tmp[j].push_back(nums[i]);
                ans.push_back(tmp[j]);
            }
            used[i] = false;
        }
        return ans;
    }
};

思考

算法是没问题的，但是在实现的时候比别的选手要慢了一些。查看题解，发现其没有使用函数的返回值来传递结果，而是使用了一个vector的引用，这样就节约了复制内存的时间。另外，使用一个path变量来记录当前的路径，也可以减少不必要的时间开销。修改后的代码如下：

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> used(nums.size(), false);
        vector<int> path;
        vector<vector<int>> ans;
        solve(nums, used, path, ans);
        return ans;
    }
private:
    void solve(vector<int> &nums, vector<bool> &used,
                              vector<int> &path, vector<vector<int>> &ans){
        if(path.size()==nums.size()){
            ans.push_back(path);
            return;
        }
        for(int i=0; i<nums.size(); i++){
            if(used[i]) continue;
            used[i] = true;
            path.push_back(nums[i]);
            solve(nums, used, path, ans);
            path.pop_back();
            used[i] = false;
        }
    }
};