Given a collection of numbers, return all possible permutations.
For example,
» Solve this problem[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]
.[解题思路]
递归,用标志位记录已使用数字。
[Code]
1: vector<vector<int> > permute(vector<int> &num) {
2: // Start typing your C/C++ solution below
3: // DO NOT write int main() function
4: vector<vector<int> > coll;
5: vector<int> solution;
6: if(num.size() ==0) return coll;
7: vector<int> visited(num.size(), 0);
8: GeneratePermute(num, 0, visited, solution, coll);
9: return coll;
10: }
11: void GeneratePermute(vector<int> & num, int step, vector<int>& visited, vector<int>& solution, vector<vector<int> >& coll)
12: {
13: if(step == num.size())
14: {
15: coll.push_back(solution);
16: return;
17: }
18: for(int i =0; i< num.size(); i++)
19: {
20: if(visited[i] == 0)
21: {
22: visited[i] = 1;
23: solution.push_back(num[i]);
24: GeneratePermute(num, step+1, visited, solution, coll);
25: solution.pop_back();
26: visited[i] =0;
27: }
28: }
29: }
No comments:
Post a Comment