专题三_穷举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[i]) continue; // 剪枝cur.push_back(nums[i]);used[i] = true;dfs(nums);used[i] = 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[idx]);dfs(nums, idx + 1);cur.pop_back();// 回溯//      不要dfs(nums, idx + 1);}
};