main.cpp

来自「我做的一些C语言练习题,里面一共有76道题目,主要用到一些计算机常用的算法,如:」· C++ 代码 · 共 78 行

/**********************************************************************************

  38. 有一集合中有 N 个元素，每个元素均为自然数。给定一个 total （假设每个
 元素值均小于total)，求满足条件的所有子集，子集中各元素之和应等于total。

  **********************************************************************************/

#include <stdio.h>
#include <malloc.h>

int n;//元素个数
int *Num;//保存所有元素
int total;//和
int *uses;//各个元素的使用情况

//显示子集
void PrintSubMuster()
{
	int i;
	int flag = 0;
	printf("{ ");
	for(i=0; i<n; i++)
	{
		if(uses[i])
		{
			if(flag)
				printf(" , ");
			else flag = !flag;
			printf("%d",Num[i]);
		}
	}
	printf(" }\n");
}

//增加一个元素到集合
void AddOne(int k,int sum)
{
	if(k == n)
	{
		if(sum == total)
		{
			PrintSubMuster();
		}		
	}
	else 
	{
		uses[k] = 1;//含有该元素
		sum += Num[k];
		AddOne(k+1,sum);
		uses[k] = 0;//不含该元素
		sum -= Num[k];
		AddOne(k+1,sum);
	}
}

void main()
{
	int i;
	//输入元素个数
	printf("请输入元素的个数n的值:");
	scanf("%d",&n);
	Num = (int*)malloc(n*sizeof(int));
	uses = (int*)malloc(n*sizeof(int));
	printf("请输入%d个自然数:\n",n);
	for(i=0; i<n; i++)
	{
		scanf("%d",&Num[i]);//输入元素
		uses[i] = 0;//初始化为未使用
	}
	//输入和值
	printf("请输入total的值:");
	scanf("%d",&total);
	//求解
	AddOne(0,0);
	//释放空间
	free(Num);
	free(uses);
}