【算法——递归回溯】

这个东西还是很重要的，直接决定了你的动态规划章节的学习深度

78. 子集

方法1：

vector<vector<int>>V;
void dfs(vector<int> v,vector<int> nums,int index)
{if(index==nums.size()) V.push_back(v);else{v.push_back(nums[index]);dfs(v,nums,index+1);v.pop_back();dfs(v,nums,index+1);}
}

方法2：

算法讲解038【必备】常见经典递归过程解析_哔哩哔哩_bilibili

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;vector<vector<int>>se;
void dfs(vector<int>nums, vector<int>pat, int i, int size)
{if (i == nums.size()){vector<int>k;for (auto i = pat.begin(); i < pat.begin() + size; i++)k.push_back(*i);se.push_back(k);}else{pat[size] = nums[i];	dfs(nums, pat, i + 1, size + 1);dfs(nums, pat, i + 1, size );}
}int main()
{vector<int>nums = { 1,2,3 };vector<int>pat(nums.size());dfs(nums, pat, 0, 0);for (auto i : se){for (auto j : i)cout << j << " ";cout << endl;}return 0;
}

90. 子集 II

#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<algorithm>
using namespace std;//首先这个子集问题有重复元素，我们在每一个节点就收。
//会出现V中有重复的情况（简单一点就是直接用set代替vector）
//还有一种方法就是用一个和nums等长的bool数组
//说这个bool前，自己画一下{1,2,2}的树形图vector<vector<int>>V;
void dfs(vector<int>v,vector<int>nums, int index,vector<bool>bol)
{V.push_back(v);for (int i = index; i < nums.size(); i++){//bool分析：//首先不能越界(i>0保护)//怎么判断是在判断是在当前树枝还是树层重复（画一下树形图，我这句话就不再抽象）//!bol[i-1]&&nums[i]==nums[i-1]就是前一个数没有选,并且当前和前一个相等。//什么时候会出现这种情况，自然是同一个树层。if (i > 0 && nums[i] == nums[i - 1] && !bol[i - 1]){//break;     //这里要注意不能是break，这里发现重复就跳跃这个数，往后面 continue;}v.push_back(nums[i]);bol[i] = 1;dfs(v, nums, i + 1,bol);v.pop_back();bol[i] = 0;}}int main()
{vector<int>nums = { 1,2,1,2 };sort(nums.begin(), nums.end());     //注意要排序vector<bool>bol(nums.size());dfs({}, nums, 0,bol);for (auto i : V){for (auto j : i)cout << j << " ";cout << endl;}return 0;
}