46.Permutations
46.Permutations
难度:Medium
Given a collection of distinct integers, return all possible permutations.
Example:
1
Input: [1,2,3]
2
Output:
3
[
4
[1,2,3],
5
[1,3,2],
6
[2,1,3],
7
[2,3,1],
8
[3,1,2],
9
[3,2,1]
10
]
Copied!
采用回溯法,想将每一位放在第一位,然后对于剩下的,将每一位放在第二位,一直循环下去。
1
class Solution {
2
vector<vector<int>>res;
3
void traceback(int n, int step)
4
{
5
if(step == n) return;
6
int len=res.size();
7
for(int i=0;i<len;i++)
8
{
9
for(int j=step+1;j<n;j++)
10
{
11
vector<int> tmp(res[i]);
12
swap(res[i][step],res[i][j]);
13
res.push_back(tmp);
14
}
15
}
16
traceback(n,step+1);
17
}
18
public:
19
vector<vector<int>> permute(vector<int>& nums) {
20
res.push_back(nums);
21
traceback(nums.size(), 0);
22
return res;
23
}
24
};
Copied!
执行用时 :12 ms, 在所有 C++ 提交中击败了98.71%的用户 内存消耗 :9.7 MB, 在所有 C++ 提交中击败了29.71%的用户
Copy link