LeetCode 46 Permutations
回溯法 LeetCode 2020-06-07 11:10:47 2022-02-22 10:54:42 675 次浏览概述
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!)
2022年2月22日时的笔记
class Solution {
public:
vector<vector<int>> ans;
vector<vector<int>> permute(vector<int>& nums) {
vector<bool> visited(nums.size());
vector<int> path;
backtrack(nums, path, visited);
return ans;
}
void backtrack(vector<int>& nums, vector<int>& path, vector<bool>& visited) {
if (path.size() == nums.size()) {
ans.push_back(path);
return;
}
for (int i = 0; i < visited.size(); i ++) {
if (!visited[i]) {
visited[i] = true;
path.push_back(nums[i]);
backtrack(nums, path, visited);
path.pop_back();
visited[i] = false;
}
}
}
};
遍历整棵决策树，因此时间复杂度 O(n! * n) = O(n!)。