专题三_穷举vs暴搜vs深搜vs回溯vs剪枝_全分列
dfs办理 全分列&子集1.全分列
link:46. 全分列 - 力扣（LeetCode）
全局变量+回溯
code
class Solution {
public:
vector<vector<int>> ans;
vector<int> cur;
vector<bool> used;
vector<vector<int>> permute(vector<int>& nums) {
// 暴力枚举
used = vector<bool>(nums.size(), false);
dfs(nums);
return ans;
}
void dfs(vector<int>& nums)
{ // 出口
if(cur.size() == nums.size())
{
ans.push_back(cur);
return;
}
// 主体
for(int i = 0; i < nums.size(); i++)
{
if(used) continue; // 剪枝
cur.push_back(nums);
used = true;
dfs(nums);
used = false;
cur.pop_back(); // 回溯
}
}
};
2.子集
link:78. 子集 - 力扣（LeetCode）
code
class Solution {
public:
vector<vector<int>> ans;
vector<int> cur;
vector<vector<int>> subsets(vector<int>& nums) {
dfs(nums, 0);
return ans;
}
void dfs(vector<int>& nums, int idx)// idx表示这次选择取舍的下标
{
// 出口
if(idx >= nums.size())
{
ans.push_back(cur);
return;
}
// 主体
// 要了
cur.push_back(nums);
dfs(nums, idx + 1);
cur.pop_back();// 回溯
// 不要
dfs(nums, idx + 1);
}
};
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]