out< "please input the number of the nodes"<<endl cin>>nodesNum cout<<"pl

//子集和数问题,用回溯法实现
#include<vector>
#include<iostream>
using namespace std;

vector<int> set(30,0);//数据集合
vector<bool> option(30,false);//标志是否选中数据
vector<bool> visited(30,false);//标记是否已经被访问


bool NextPosAbideByRule( int currentIndex,int &tempsum, int sum ,int n)
{
	//对第currentIndex个数据进行选择,要么选中要么不选中,但必须符合规则
    if(currentIndex > n)        //如果没有这一步则运行时发生异常
		return false;
	if(!visited.at(currentIndex))//没有被访问
	{
        option.at(currentIndex) = 1;
	    visited.at(currentIndex) = true;
	   if( tempsum + set.at(currentIndex) > sum )//不符合规则
          option.at(currentIndex) = 0;	         //则选择另一种可能性
	     return true;
	}
	else//访问过了
	{
		if( option.at(currentIndex) == 0)
		{
            visited.at(currentIndex) = false;
		    return false;
		}
		else //option本来为1,现在要为0
		{
			tempsum = tempsum - set.at(currentIndex);
			option.at(currentIndex) = 0;
			return true;
		}
	}

	
    

    



}

void OutPut( int wi)
{   
	cout<<"--------------------------"<<endl;
	int i;
	for( i = 1; i <= wi; ++i)
	{
		if(option.at(i))
			cout<<set.at(i)<<"  ";
	}
   
}
void SubsetSum( int n,int sum)
{
	int workIndex = 1; //工作下标
	int tempsum =0;
	while( workIndex > 0 )
	{
		if( NextPosAbideByRule( workIndex,tempsum,sum,n ) )
		{
			if(option.at(workIndex))
				tempsum += set.at(workIndex);

			if( tempsum == sum)  //一条路径找到
			{ 
				OutPut(workIndex);        //输出
			}
			else 
				workIndex ++;
		}
		else
			workIndex --;
	}//while

}

int main()
{
		int totalNum;
		cout<< "please input the total number of the set  "<<endl;
		cin >> totalNum;
		cout<<"please input the values of the set "<<endl;
		int i,value;
		for( i = 1;i <= totalNum;i++)
		{
			cin>>value;
			set.at(i) = value;
		}
		int sum;
		cout<<"please input the Sum"<<endl;
		cin>>sum;
		SubsetSum(totalNum,sum);
		cout<<"------------------"<<endl;

}