题目:
给定一个没有重复数字的序列,返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
解题思路:
递归求解,难点在于输出一个排列后怎么回溯。
记录当前序列的长度lever,当lever和nums长度相等时,即为一个排序out。
使用visited数字来标识某点是否被访问过。
以上的lever,out,visited都需要回溯。
回溯的方法是:在递归语句前设定某状态,在递归语句后取消该状态。
代码:
class Solution {
public: vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> out;
vector<int> visited(nums.size(), );
perDFS(nums,,visited,out,ans);
return ans;
} void perDFS(vector<int> nums, int lever, vector<int> &visited, vector<int> &out, vector<vector<int>> &ans) {
if(lever == nums.size()){
ans.push_back(out);
return ;
}
for(int i=; i<nums.size(); ++i){
if(visited[i])
continue;
visited[i] = ; //1、递归函数前设定visited和out 为某状态
out.push_back(nums[i]);
perDFS(nums,lever+,visited,out,ans); //2、递归语句,lever在参数中回溯了
out.pop_back(); //3、递归函数后取消visited和out的某状态
visited[i] = ;
}
}
};