//說明:子集和問題
//給定一個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;
}