5-1.cpp

利用回溯法求解子集和问题的C++实现 给定正整数集合S和正整数c计算出子集和s1使得子集合之和为c

#include <iostream>
using namespace std;

const int n = 10;  
int time = 0;  
int s[n] = {2,3,5,4,1,6,7,8,9,10};		
int c = 10;			
int sum = 0;			
int is_not[n] = {0};		//确定集合中数字是否在子集合中，值为0则在，值为1则不在，初始化为0

void backtrack(int [], int, int);

void main()
{
	int i = 0;
	backtrack(s, n, i);
	
	if(time==0)
		cout<<"No Solution!"<<endl;
}

void backtrack(int *p , int n, int i)			//回溯法搜索子集和
{
	if(sum == c)			//如果当前子集和与c相等，则输出该子集和中的整数
	{
		for(int j=0; j<n; ++j)
		{
			if(is_not[j]==1)
			{
				cout<<s[j]<<"  ";
			}
		}
		cout<<endl;
		time++;
	}
	else
	{
		if(sum + p[i] <= c)			
		{
			for(int k=1; k>=0; --k)			
			{
				if(k==1)			//将当前节点值加入到子集和中，并递归调用backtrack，将i的值自加
				{
					sum += s[i];
					is_not[i]=1;
				}
				else				//不将当前节点值加入到子集和中，并递归调用backtrack，将i的值自加
				{
					sum -= s[i];
					is_not[i]=0;
				}
				backtrack(p, n, i+1);
			}   
		}  
	}
	
}