在暴力求解算法中,子集生成问题是一个很重要的算法,在一个数组中找到各种子集,然后筛选出符合题目条件的子集,比如n-sum等问题,现在写一个位向量法生成子集的通用模板
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;
/*visit是一个标记数组,判断是否选择该位置的数*/
void create_subset(vector<int> &arry,int cur,int n,char visit[])
{
if(cur == n)
{
/*在这里可以加一个判断条件,看是否满足题目所给的条件*/
for(int i = 0; i < n; i++)
if(visit[i])
printf("%d ",arry[i]);
printf("\n");
return;
}
visit[cur] = 0;
create_subset(arry,cur+1,n,visit);
visit[cur] = 1;
create_subset(arry,cur+1,n,visit);
}
int main()
{
int n;
cin>>n;
vector<int> arry;
char visit[n];
arry.resize(n);
for(int i = 0; i < arry.size(); i++)
cin>>arry[i];
create_subset(arry,0,n,visit);
return 0;
}