#include <iostream>#include <stdio.h>#include <vector>#include <algorithm>using namespace std;/*問題:Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.The same repeated number may be chosen from C unlimited number of times.Note:All numbers (including target) will be positive integers.The solution set must not contain duplicate combinations.For example, given candidate set [2, 3, 6, 7] and target 7, 分析:這是程序員面試金典的一道題目。求組成數(shù)的所有組合。應該是用遞歸做。之前是n分的硬幣用25,10,5,1的硬幣表示分別枚舉i * denom <= total時，i從0到k的情況，然后遞歸做2 3 6 7此題應該也是用這種方式輸入:4(數(shù)組元素個數(shù)) 7(目標值)2 3 6 74 62 3 6 72 72 6輸出:7,2 2 36,3 3,2 2 2no result關(guān)鍵:1 前半部分求解結(jié)果，前半部分 與 后半部分結(jié)果 進行笛卡爾積 即為最終結(jié)果int curCandidate = candidates.at(curCandidateIndex);vector<vector<int>> results;//后半部分遞歸求解結(jié)果vector<int> result;//前半部分求解結(jié)果，前半部分 與 后半部分結(jié)果 進行笛卡爾積 即為最終結(jié)果for(int i = 0 ; i * curCandidate <= target ; i++){	result.clear();//清空上一次結(jié)果	for(int j = 0 ; j < i ; j++)	{		result.push_back(curCandidate);	}	results = combineSum(candidates , target -  i * curCandidate , curCandidateIndex + 1 );//得到多個結(jié)果需要和當前結(jié)果進行笛卡爾積拼接	int size = results.size();	//進行笛卡爾積拼接	for(int k = 0 ; k < size ; k++)	{		results.at(k).insert(results.at(k).end() , result.begin() , result.end());//插入到后面，前面是最小部分		totalResults.push_back(results.at(k));	}	//如果當前直接等于結(jié)果集i * curCandidate = target,直接壓入結(jié)果中	if(i * curCandidate == target)	{		totalResults.push_back(result);	}}return totalResults;*/bool compare(int a, int b){	return a > b;}class Solution {public:	vector<vector<int>> combineSum(vector<int>& candidates, int target , int curCandidateIndex)	{		vector< vector<int> > totalResults;		if(candidates.empty() || target <= 0 || curCandidateIndex < 0 || curCandidateIndex >= candidates.size())		{			return totalResults;		}		int curCandidate = candidates.at(curCandidateIndex);		vector<vector<int>> results;//后半部分遞歸求解結(jié)果		vector<int> result;//前半部分求解結(jié)果，前半部分 與 后半部分結(jié)果 進行笛卡爾積 即為最終結(jié)果		for(int i = 0 ; i * curCandidate <= target ; i++)		{			result.clear();//清空上一次結(jié)果			for(int j = 0 ; j < i ; j++)			{				result.push_back(curCandidate);			}			results = combineSum(candidates , target -  i * curCandidate , curCandidateIndex + 1 );//得到多個結(jié)果需要和當前結(jié)果進行笛卡爾積拼接			int size = results.size();			//進行笛卡爾積拼接			for(int k = 0 ; k < size ; k++)			{				results.at(k).insert(results.at(k).end() , result.begin() , result.end());//插入到后面，前面是最小部分				totalResults.push_back(results.at(k));			}			//如果當前直接等于結(jié)果集i * curCandidate = target,直接壓入結(jié)果中			if(i * curCandidate == target)			{				totalResults.push_back(result);			}		}		return totalResults;	}    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {        //必須確保候選值從大到小排序		sort(candidates.begin() , candidates.end() , compare );		int curCandidateIndex = 0;		vector<vector<int>> results = combineSum(candidates, target , curCandidateIndex);		return results;    }};void PRint(vector<vector<int>>& results){	if(results.empty())	{		cout << "no result" << endl;		return;	}	int size = results.size();	for(int i = 0 ; i < size ; i++)	{		int len = results.at(i).size();		for(int j = 0 ; j < len ; j++)		{			cout << results.at(i).at(j) << " ";		}		cout << ",";	}	cout << endl;}void process(){	int num;	vector<int> nums;	int target;	int value;	Solution solution;	vector< vector<int> > results;	while(cin >> num >> target)	{		nums.clear();		for(int i = 0 ; i < num ; i++)		{			cin >> value;			nums.push_back(value);		}		results = solution.combinationSum(nums , target);		print(results);	}}int main(int argc , char* argv[]){	process();	getchar();	return 0;}