编程之美—— Combination Sum

递归思想：

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;

vector<vector<int> >  m_vecRet;


void combination(const vector<int> &num, size_t idx, vector<int> &curr, int target)
{
	if (target == 0)
	{
		m_vecRet.push_back(curr);
	}
	else
	{
		for (size_t i = idx; i < num.size(); ++i)
		{
			if (i != idx && num[i] == num[i - 1])
			{
				continue;
			}

			if (target >= num[i])
			{   
				curr.push_back(num[i]);
				combination(num, i , curr, target - num[i]);
				curr.pop_back();
			}
		}
	}
}

vector<vector<int> > Combination_Sum(vector<int> &num, int target) 
{
	vector<int> vecTmp; 
	m_vecRet.clear();
	sort(num.begin(), num.end());
	combination(num, 0, vecTmp, target);
	return m_vecRet;
}

int main()
{
	int sum = 18;
	int data[3] = {7,2,3};
	vector<int> res(data, data + sizeof(data)/sizeof(int));
	vector<vector<int>> des;
	des = Combination_Sum(res,sum);
	for(int i = 0; i < des.size(); i++)
	{
		for(vector<int>::iterator it = des[i].begin(); it != des[i].end();it++)
		{
			cout<<*it<<" ";
		}
		cout<<endl;
	}

	cin.get();
	return 0;
}