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] ]
方法：可以在原来的数组上进行改进，不需要开辟过多的额外空间。
class Solution { private: void next(vector<int>& now){ int start = -1 ; for(int i = now.size() - 2; i >=0; --i){ if(now[i]<now[i+1]){ start = i; break; } } if(start==-1) sort(now.begin(),now.end()); else{ for(int i = now.size() - 1; i >= start ; --i){ if(now[i]>now[start]){ swap(now[i],now[start]); break; } } reverse(now.begin() + start + 1,now.end()); } } public: vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> res; vector<int> buffer(nums.begin(),nums.end()); res.push_back(buffer); next(buffer); while(buffer!=nums){ res.push_back(buffer); next(buffer); } return res; } };