今日做luogu枚举题单，发现很多题目共性很强
类似题目在leetcode上也有不少
共性
- 从一个序列中按规定选取若干元素
- “ 做选择 ” 产生了一颗选择二叉树
- 题目数据不强，暴力遍历即可找出答案
细节差异
- 选取元素的限制：数量，顺序，大小（子集，组合，排列的区别）
- 子集：不限制数量，顺序
- 组合：元素数量一定的子集
- 排列：数量最大，对顺序敏感的子集
- 根据题目情境遍历二叉树，在特定的位置进行比较，修改
注：还有原序列是否含重复元素，同一元素是否可以重选等问题
习题
以下题目框架几乎完全一样，主要关注细节差异
luogu P1157
#include<bits/stdc++.h>
using namespace std;
namespace IO{template<typename T>void read(T&x){x=0;bool f=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}if(f)x=-x;}void read(char&c){c=getchar();while(isspace(c))c=getchar();}void read(string&s){s.clear();char ch=getchar();while(isspace(ch))ch=getchar();while(!isspace(ch)&&ch!=EOF){s+=ch;ch=getchar();}}template<typename T,typename...Args>void read(T&first,Args&...rest){read(first);read(rest...);}template<typename T>void wr(T x){if(x==0){putchar('0');return;}if(x<0){putchar('-');x=-x;}char stk[20];int top=0;while(x){stk[++top]=x%10+'0';x/=10;}while(top){putchar(stk[top--]);}}void wr(const char c){putchar(c);}void wr(const string&s){for(char c:s)putchar(c);}void wr(const char*s){while(*s)putchar(*s++);}template<typename T>void wr(const T&x,char sep){wr(x);putchar(sep);}template<typename T,typename...Args>void wr(const T&first,const Args&...rest){wr(first);((putchar(' '),wr(rest)),...);}}using namespace IO;
typedef long long ll;
typedef pair<int,int> pii;vector<vector<int>>ans;
vector<int>path;
void dfs(int x,int n,int k){if((int)path.size()==k){ans.push_back(path);return;}for(int i=x;i<=n;i++){path.push_back(i);dfs(i+1,n,k);path.pop_back();}
}
void solve(){int n,r;read(n,r);dfs(1,n,r);for(auto x:ans){for(int i=0;i<r;i++){cout<<setw(3)<<x[i];}wr('\n');}
}
int main(){int T=1;//read(T);while(T--){solve();}
}
luogu P1036
bitset<100000000>isp;//埃氏筛，预处理素数
vector<int>x(25);
int n,k,ans=0;
void init(){for(int i=0;i<n;++i)read(x[i]);isp.set();isp[0]=isp[1]=0;for(int i=2;i*i<=100000000;++i){if(isp[i]){for(int j=i*i;j<=100000000;j+=i)isp[j]=0;}}
}
void dfs(int indx,int cnt,int sum){if(cnt==k){if(isp[sum])ans++;return ;}for(int i=indx;i<n;i++){dfs(i+1,cnt+1,sum+x[i]);}
}
void solve(){read(n,k);init();dfs(0,0,0);wr(ans);
}
luogu P2089
vector<vector<int>>ans;
vector<int>path;
void dfs(int sum,int tar){if(path.size()==10){if(sum==tar)ans.push_back(path);return;}for(int i=1;i<=3;i++){path.push_back(i);dfs(sum+i,tar);path.pop_back();}
}
void solve(){int n;read(n);if(n>30||n<10){wr(0);return;}dfs(0,n);wr(ans.size(),'\n');for(auto x:ans){for(int i=0;i<10;i++)wr(x[i],i==9?'\n':' ');}
}
luogu P2392
void dfs(int& ans,vector<int>&a,int indx,int A,int B){if(indx==(int)a.size()){ans=min(ans,max(A,B));return;}dfs(ans,a,indx+1,A+a[indx],B);dfs(ans,a,indx+1,A,B+a[indx]);
}
void solve(){vector<int>s(4);for(int i=0;i<4;i++)read(s[i]);int ans=0;for(int i=0;i<4;++i){vector<int>a(s[i]);for(int j=0;j<s[i];++j)read(a[j]);int t=1200;dfs(t,a,0,0,0);ans+=t;}wr(ans);
}
luogu P2036
int n,a[10],b[10];
int ans=INT_MAX;
void dfs(int indx,int A,int B){if(indx!=0)ans=min(ans,abs(A-B));for(int i=indx;i<n;++i){dfs(i+1,A*a[i],B+b[i]);}
}
void solve(){read(n);for(int i=0;i<n;++i)read(a[i],b[i]);dfs(0,1,0);wr(ans);
}
leetcode 90
class Solution {vector<vector<int>>ans;vector<int>path;
public:vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort(nums.begin(),nums.end());dfs(0,nums);return ans;}void dfs(int indx,vector<int>nums){ans.push_back(path);for(int i=indx;i<(int)nums.size();++i){if(i>indx&&nums[i]==nums[i-1])continue;path.push_back(nums[i]);dfs(i+1,nums);path.pop_back();}}
};
leetcode 47
class Solution {vector<vector<int>>ans;vector<int>path;
public:vector<vector<int>> permuteUnique(vector<int>& nums) {vector<bool>vis(nums.size(),0);sort(nums.begin(),nums.end());dfs(nums,vis);return ans;}void dfs(vector<int>&nums,vector<bool>&vis){if(path.size()==nums.size()){ans.push_back(path);return;}for(int i=0;i<(int)nums.size();++i){if(i>0&&nums[i]==nums[i-1]&&!vis[i-1])continue;if(!vis[i]){vis[i]=1;path.push_back(nums[i]);dfs(nums,vis);vis[i]=0;path.pop_back();}}}
};
leetcode 40
class Solution {vector<vector<int>>ans;vector<int>path;
public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(),candidates.end());dfs(0,0,candidates,target);return ans;}void dfs(int indx,int sum,vector<int>& candidates, int target){if(sum==target){ans.push_back(path);return ;}if(sum>target)return;for(int i=indx;i<(int)candidates.size();i++){if(i>indx&&candidates[i]==candidates[i-1])continue;path.push_back(candidates[i]);dfs(i+1,sum+candidates[i],candidates,target);path.pop_back();}}
};
leetcode 39
class Solution {vector<vector<int>>ans;vector<int>path;
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {dfs(0,0,candidates,target);return ans;}void dfs(int indx,int sum,vector<int>& candidates, int target){if(sum==target){ans.push_back(path);return ;}if(sum>target)return;for(int i=indx;i<(int)candidates.size();i++){path.push_back(candidates[i]);dfs(i,sum+candidates[i],candidates,target);path.pop_back();}}
};