LeetCode Permutations

Given a collection of 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], and[3,2,1].

题意：生成所有的序列。

思路：一个用stl，一个就是dfs，每次固定前cur个，，然后依次和之后的数交换

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

class Solution {public:void dfs(vector<int> &num, vector<vector<int> > &ans, int cur, int n) {if (cur == n) {ans.push_back(num);}for (int i = cur; i < n; i++) {swap(num[cur], num[i]);dfs(num, ans, cur+1, n);swap(num[cur], num[i]);}}vector<vector<int> > permute(vector<int> &num) {vector<vector<int> > ans;int n = num.size();dfs(num, ans, 0, n);return ans;}};

真凉爽啊！青山绿水映入我的眼中，景色怡人啊！