穷举vs暴搜vs深搜vs回溯vs剪枝

2024-01-01 00:20

文章标签 vs 穷举回溯剪枝

本文主要是介绍穷举vs暴搜vs深搜vs回溯vs剪枝，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

欢迎来到Cefler的博客😁
🕌博客主页：那个传说中的man的主页
🏠个人专栏：题目解析
🌎推荐文章：题目大解析（3）

在这里插入图片描述

👉🏻全排列

原题链接：全排列
在这里插入图片描述

mycode:

class Solution {
public:vector<vector<int>> ret;vector<int> path;bool check[7];//检查该位置是否被用过了，true说明被用过了 void dfs(vector<int>& nums){if(nums.size()==path.size())//说明此时已经组成一个序列了{ret.push_back(path);return;}for(int i = 0;i<nums.size();i++){if(check[i]==false)//此时还没被用过{path.push_back(nums[i]);check[i] = true;dfs(nums);//回溯清空现场，将dfs下层插入的元素pop掉path.pop_back();check[i] = false;}}}vector<vector<int>> permute(vector<int>& nums) {dfs(nums);return ret;}
};

👉🏻子集

原题链接：子集

mycode:

class Solution {
public:vector<vector<int>> ret;vector<int> part;void dfs(vector<int>& nums,int n){//可以选择插入或选择不插入for(int i = n;i<nums.size();i++){part.push_back(nums[i]);dfs(nums,++n);//回溯清理现场part.pop_back();}ret.push_back(part);}vector<vector<int>> subsets(vector<int>& nums) {int n = 0;dfs(nums,n);return ret;}
};

在这里插入图片描述
解法二：

mycode:

class Solution {
public:vector<vector<int>> ret;vector<int> part;void dfs(vector<int>& nums,int n){//可以选择插入或选择不插入for(int i = n;i<nums.size();i++){part.push_back(nums[i]);dfs(nums,i+1);//回溯清理现场part.pop_back();}ret.push_back(part);}vector<vector<int>> subsets(vector<int>& nums) {int n = 0;dfs(nums,n);return ret;}
};