首页 > 代码库 > C++ P2832 生成可重集的子集

C++ P2832 生成可重集的子集

#include<iostream>
#include<cstdio>
using namespace std;

int n,m,vis[15],num[15];//vis[i]代表数字i在全集中出现的总次数,num[i]为i在子集中出现的次数;

void data_in()
{
  scanf("%d%d",&n,&m);
  int x;
  for(int i=1;i<=n;i++)
  {
    scanf("%d",&x);
    vis[x]++;
  }
}

void ans_out()
{
  for(int i=1;i<=10;i++)
  {
    int x=num[i];
    while(x-->0) printf("%d ",i);
  }
  printf("\n");
  return;
}

void run(int x,int len)//考察数字x是否使用,len为之前用过的数字的数目;
{
  if(x>10){
    if(len==m) ans_out();
    return;
  }
  for(int i=vis[x];i>=0;i--)if(len<=m)
  {
    num[x]=i;
    run(x+1,len+i);
  }
}

int main()
{
  // freopen("test.in","r",stdin);
  // freopen("test.out","w",stdout);
  data_in();
  run(1,0);
  return 0;
}

C++ P2832 生成可重集的子集