LeetCode 46 Permutations
https://leetcode.com/problems/permutations/
第一次提交
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> permute(vector<int>& nums) {
vector<int> track;
backtrack(nums, track);
return res;
}
private:
void backtrack(vector<int>& nums, vector<int>& track) {
// Deal with the end case
if(track.size()==nums.size()) {
res.push_back(track);
return;
}
for(auto num:nums){
// Check whether the current num has been used
if(find(track.begin(), track.end(), num)!=track.end()){ // Has been used
continue;
}
track.push_back(num);
backtrack(nums, track);
track.pop_back();
}
}
};
第二次提交
针对第一次提交,其中的检查路径中是否已经包含该节点的方式可以改进。
因为我们是按顺序访问 nums 的,因此只需要记录一下当前访问到那个节点就好,之后循环遍历的时候直接从该节点开始。
除此之外,我们知道 track 的用途是记录当前已访问过的节点,其实直接用 nums 存就好,我们就按照访问顺序去存储,访问该路径后回溯回来就好。
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> permute(vector<int>& nums) {
backtrack(nums, 0);
return res;
}
private:
void backtrack(vector<int>& nums, int startIndex) {
// Deal with the end case
if(startIndex >= nums.size()) {
res.push_back(nums);
return;
}
for(int i=startIndex;i<nums.size();++i){
swap(nums[startIndex], nums[i]);
backtrack(nums, startIndex+1);
swap(nums[startIndex], nums[i]);
}
}
};
分析总结
在该题目中,我们对搜索树进行了剪枝,每向下一层少一种选择,则总的路径个数为(设 n 为 nums 的尺寸):n! 复杂度也即 O(n!)