leet 46 全排列
解题思路
还是全排列的板子题
Class Solution {
private:
vector<vector<int>> result;
vector<int> ans;
public:
void backingtrack(...){
if (){
...
return;
}
for () {
...
}
}
};
和基础不同的是,多了一个像dfs的visit数组 ,但是官方解答真的666
代码
class Solution {
private:
vector<vector<int>> result;
vector<int> ans;
void backtracking(vector<int>& nums, vector<bool>& used) {
if (ans.size() == nums.size()) {
result.push_back(ans);
return;
}
for (int i = 0 ; i < nums.size(); i++) {
if (used[i] == false) {
used[i] = true;
ans.push_back(nums[i]);
backtracking(nums,used);
used[i] = false;
ans.pop_back();
}
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<bool> used(nums.size(), false);
backtracking(nums, used);
return result;
}
};
官方解答
没有开辟新的数组来判断是否访问过,而是直接在原始数组中左交换,和startIndex有点类似的做法
class Solution {
public:
void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len){
// 所有数都填完了
if (first == len) {
res.emplace_back(output);
return;
}
for (int i = first; i < len; ++i) {
// 动态维护数组
swap(output[i], output[first]);
// 继续递归填下一个数
backtrack(res, output, first + 1, len);
// 撤销操作
swap(output[i], output[first]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int> > res;
backtrack(res, nums, 0, (int)nums.size());
return res;
}
};
作者:LeetCode-Solution
链接:https://leetcode.cn/problems/permutations/solution/quan-pai-lie-by-leetcode-solution-2/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
标签:used,nums,res,之全,算法,vector,回溯,output,first
From: https://www.cnblogs.com/tsqo/p/17182582.html