sumofsub.cpp

来自「子集和数问题」· C++ 代码 · 共 46 行

#define MAXNUM 100 
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;

bool x[MAXNUM];
int M,n,r=0,w[MAXNUM];

void sumofsub(int s,int k,int r){
//左子树
	x[k]=1;
	if (s+w[k]==M){
		for(int i=1;i<=k;i++)
			printf("%d",x[i]);
			printf("\n");
		}
	else
		if (s+w[k]+w[k+1]<=M)
			sumofsub(s+w[k],k+1,r-w[k]);
//右子树
		if (s+r-w[k]>=M&&s+w[k+1]<=M){
			x[k]=0;
			sumofsub(s,k+1,r-w[k]);
		}
}

int main(){
	printf("input n=? ");
	scanf("%d",&n);
	printf("input M=? ");
	scanf("%d",&M);
	printf("input w[]=?\n");
	for(int i=1;i<=n;i++)
	{
		printf("w[%d]=",i);
		scanf("%d",&w[i]);
	}
	for(i=1;i<=n;i++)
		r=r+w[i];
	w[n+1]=r;
	sumofsub(0,1,r);
	return 0;
}