main.cpp

说明:子集和问题 给定一个n个整数的集合X = {x1, x2, …, xn}和整数Y

//说明:子集和问题
//给定一个n个整数的集合X = {x1, x2, …, xn}和整数Y，找出和等于Y的X的子集subX。
//比如说，如果X ={10,20,30,40,50,60} 和 Y = 60
//则有三种不同长度的解，它们分别是
//subY = {10，20，30}，{20，40} 和{60}

//这也是回溯法的一个典型的例子

#pragma once
#include <windows.h>
#include <vector>
#include <iostream>
using namespace std;
#define N 20
int set[N] = {10,20,30,40,50,60,100,5,8,2,13,7,7,8,16,4,1,56,55,23};
int sum = 150;

typedef struct Node
{
	int ID;//记录当前的节点在数组中的位置
	int number;//记录当前节点的数值
};

void printResult(const std::vector<Node> & nums)
{
	
	if(nums.size())
	{
		cout<<"(";
	}
	int checkSum = 0;
	for(std::vector<Node>::const_iterator numsIt = nums.begin();numsIt != nums.end();numsIt++)
	{
		
		if(numsIt != nums.end() - 1)
		{
			cout<<(*numsIt).number<<" + ";
		}
		else
		{
			cout<<(*numsIt).number<<")"<<" = "<<sum<<endl;
		}
		checkSum += (*numsIt).number;
	}
	if(checkSum != sum)
	{
		_ASSERT(FALSE);
	}
}

void SubSetSum()
{
	std::vector<Node> nums;
	int curSum = 0;
	Node curNode;
	curNode.ID = -1;
	curNode.number = 0; 
	nums.push_back(curNode);
	int k = 0;
	while(nums.size()!= 0)
	{
		for(int i = k;i < N;i++)
		{
			curNode.ID = i;
			curNode.number = set[i];
			curSum = curSum + set[i];
			nums.push_back(curNode);
			if(curSum == sum)
			{
				printResult(nums);
				curSum = curSum - set[i];
				nums.pop_back();
			}
			else if(curSum > sum)
			{
				curSum = curSum - set[i];
				nums.pop_back();
			}
		}
		k = nums.back().ID + 1;
		int last = nums.back().number;
		nums.pop_back();//回溯
		curSum = curSum - last;
	}
	return;
}

int main()
{
	int startTime = ::GetTickCount();
	SubSetSum();
	int endTime = ::GetTickCount();
	cout<<"运行时间:"<<""<<endTime - startTime<<"ms"<<endl;
	system("pause");
	return 0;
}