Permutations (Medium)

Description

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].

Analysis

= =。算法书上讲的例题。。其实可以直接用next_permutation
复习一下。

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//C++
class Solution {
    vector<vector<int> > ans;
public:
    vector<vector<int> > permute(vector<int> &num) {
        int n = num.size();
        dfs(num,0,n);
        return ans;
    }
    void dfs(vector<int> &num,int step,int n){
        if(step>=n){
            ans.push_back(num);
            return;
        }
        for(int i = step;i<n;i++){
            swap(num[step], num[i]);
            dfs(num,step+1,n);
            swap(num[step], num[i]);
        }
    }
};