46. Permutations
Description
Given a collection of distinct 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],
[3,2,1]
]
Analysis
这道题和之前遇到的回溯法应用有较大的不同，此题要求给出一个字符数组的全排列。
考虑手工计算全排列的过程，从序列中选择第一个数字，之后固定第一个数字，从后续中再选择数字，之后再固定第二个数字，选择第三个数字……循环往复直到获得一个长度与原字符数组相同的的新数组。
所以与之前的回溯法的实现不同，在首轮迭代的过程中，先将第一个数字也就是nums[0]压入栈中，使其固定，构造以nums[0]开头的所有排列；那么之后将以nums[1]为开头，构造所有排列，在此之前，需要将nums[0]从栈中弹出。
代码如下:
code
class Solution {
void backtracking(vector<vector<int>> & res,vector<int> & temp,vector<int> & nums){
if(temp.size()==nums.size()){
res.push_back(temp);
return;
}
for(int i=0;i<nums.size();++i){
if(find(temp.begin(),temp.end(),nums[i])!=temp.end()) continue;
temp.push_back(nums[i]);
backtracking(res,temp,nums);
temp.pop_back();
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> res;
vector<int> temp;
backtracking(res,temp,nums);
return res;
}
};