1.题目描述
给定一个 没有重复 数字的序列，返回其所有可能的全排列。 示例:
2.回溯法
1.求出所有可能出现在第一个位置的元素，即把第一个元素和后面所有元素交换 2.固定第一个元素，求后面所有元素的排列 3.固定前两个元素… 4.然后递归地处理后面的元素 5.回溯的时候要交换回元素
3.代码
class Solution {
public:
vector
<vector
<int>> permute(vector
<int>& nums
) {
vector
<vector
<int>> res
;
if(nums
.empty()){
return res
;
}
backTrack(nums
, res
, 0);
return res
;
}
void backTrack(vector
<int>& nums
, vector
<vector
<int>> & res
, int begin
){
if(begin
== nums
.size() - 1){
res
.push_back(nums
);
}
for(int i
= begin
; i
< nums
.size(); ++i
){
if(i
!= begin
&& nums
[i
] == nums
[begin
]){
continue;
}
swap(nums
[begin
], nums
[i
]);
backTrack(nums
, res
, begin
+ 1);
swap(nums
[begin
], nums
[i
]);
}
}
};
4.复杂度分析
时间复杂度：O(n * n!)，其中 n 为序列的长度。 空间复杂度：O(n)
