一般而言，对类组合数问题，朴素的枚举法实现中，往往有几个未知的东西，我们就来几重循环。再根据提议处理循环范围，在最里层的循环中加入判断语句，判断该组合是否满足条件。
枚举对象一多，就会写出比较复杂的代码，时间效率也不太优秀。
pdf
常见枚举优化思路
- 减少枚举对象
- 剪枝
减少枚举对象
可以利用数学性质来进行对象的优化。例如有三个未知的对象，限制条件为总量固定为N，按以往的处理可以写出三重循环，每重循环的范围限制0~N。复杂度就为$O(N^3)$。
若我们确定了前两个数的个数i,j。第三个数利用总量固定的特性，可求出第三个数的数量：N-i-j 。那么就只需写出两重循环，复杂度可降为$O(N^2)$。
剪枝
对于当前分支已经明显不可能满足条件的话，可以直接结束当前分支，思考另一种分支。
hash优化
对于每个数字是否存在，除了对所有的数字进行遍历，依次判断以外，在数字范围不太大的前提下，可以利用hash的思想简化判断过程。将遍历的$O(n)$降为调用的$O(1)$。
例题讲解
2022数对
方法1
朴素枚举,复杂度为$O(n^2)$
#include <iostream>
using namespace std;
const int N=1e4+5;
int a[N];//存储不同的整数
int main(){
int n,cnt=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];//输入n个数字
}
for(int i=1;i<=n;i++){//遍历第1个数字
for(int j=i+1;j<=n;j++){//遍历第2个数字，为了避免重复，设定下标从j+1开始
if(a[i]+a[j]==2022){//判断 数对和 是否满足要求
cnt++;//统计个数
}
}
}
cout<<cnt;//输出答案
return 0;
}方法2
优化。复杂度$O(n)$
数值范围是$[-10000,10000]$ 。范围不太大，可以将值映射到下标，用于判断某个值是否出现。注意下标最小从0开始，所以映射的范围为$[0,20000]$ 只需将输入的值$+10000$即可实现偏移映射。
cin>>x;
vis[x+10000]=1;已知总和为2022
当输入x，若能组合形成数对，另一个数值确定为2022-x。
只需判断这个数在之前出现过没即可。
#include<iostream>
using namespace std;
const int N=1e4+5;
bool vis[2*N];
int main(){
int n,x,cnt=0;
cin>>n;
for(int i=1;i<=n;i++){
cin>>x;
int y=2022-x;//求能形成数对的另一个可能值
if(y>=-10000&&y<=10000&&vis[y+10000]){//另一个数在范围内，且该数在之前出现过
cnt++;
}
vis[x+10000]=true;//标记x对应的数出现过
}
cout<<cnt;//输出答案
return 0;
}珠心算测验
方法1
朴素枚举，复杂度$O(n^3)$。
#include <iostream>
#include <algorithm>
using namespace std;
int n,cnt;
int a[105];
bool sum[30005];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+1+n);//从小到大到排序
for(int i=1;i<=n;i++){//找第一个数
for(int j=i+1;j<=n;j++){//找第二个数
for(int k=j+1;k<=n;k++){//找第三个数 和
if(a[i]+a[j]==a[k]&&!sum[a[k]]){//hash判断，防止重复
sum[a[k]]=true;
cnt++;
}
}
}
}
cout<<cnt;
return 0;
}方法2
将所有的两个数字的组合对应的和进行标记。再看输入的数字中是否有被标记过的和，进行统计即可。
复杂度$O(n^2)$
#include <iostream>
using namespace std;
int n,cnt;
int a[105];
bool sum[20005];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
for(int j=1;j<i;j++){//与之前的1~i-1的数进行组合
sum[a[i]+a[j]]=true;//将组合的和进行标记
}
}
for(int i=1;i<=n;i++){//遍历输入的数，统计是集合中其他两个数的和的个数
if(sum[a[i]]) cnt++;
}
cout<<cnt;
return 0;
}砝码称重
方法1
枚举每种砝码的可能的使用个数，6种砝码就是6重循环。
复杂度$O(x_1\times x_2\times x_3\times x_4\times x_5 \times x_6)$
#include<iostream>
using namespace std;
int num[7];
int w[1001];
int main() {
int i, j, k, l, m, n, cnt = 0, sum;
//按照顺序输入不同砝码的数量
for (i = 1; i <= 6; i++) {
cin >> num[i];
}
//进行数量枚举
for (i = 0; i <= num[1]; i++) {
for (j = 0; j <= num[2]; j++) {
for (k = 0; k <= num[3]; k++) {
for (l = 0; l <= num[4]; l++) {
for (m = 0; m <= num[5]; m++) {
for (n = 0; n <= num[6]; n++) {
if (i + j + k + l + m + n >= 1) {
sum = i * 1 + j * 2 + k * 3 + l * 5 + m * 10 + n * 20;
w[sum] = 1;//标记总和
}
}
}
}
}
}
}
//找1~1000中能称出来的重量
for (i = 1; i <= 1000; i++) {
if (w[i] == 1) {//判断重量i是否能被砝码表示
cnt++;
}
}
cout << cnt;
return 0;
}
方法2
hash结合背包的思路。
每次你使用一个砝码就在之前的砝码组合出的重量上再放一个，标记新重量为可组合的。
需要注意的是，当前状态只能由之前的状态决定，你当前能组合的重量基于你之前可组合出的重量。所以遍历重量时从大到小来，因为新重量总是在原来的组合出的重量上增加砝码，重量总是增加的，从小到大的话，会影响之后的判断。
复杂度$O(x\times m)$ x-个数，m-总重量
#include <iostream>
#include <cstring>
using namespace std;
bool wei[1005];
int num[10]={0,1,2,3,5,10,20};
int main(){
int x,ans=0;
for(int i=1;i<=6;i++){
cin>>x;
for(int j=1;j<=x;j++){
for(int k=1000;k>=0;k--){//注意顺序 以免组合出的新重量，影响之后的处理
if(wei[k]){//之前已经能组合出重量k
wei[k+num[i]]=true;//在之前的基础上，再加一个砝码形成新重量k+num[i]
}
}
if(j==1){
wei[num[i]]=true;//标记num[i]能表示的重量
}
}
}
for(int i=0;i<=1000;i++){//遍历总重量范围内所有的可表达的重量
ans+=wei[i];
}
cout<<ans;
return 0;
}