#include <iostream>#include <stdio.h>#include <vector>#include <map>#include <algorithm>using namespace std;/*問題:Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.Each number in C may only be used once in the combination.Note:All numbers (including target) will be positive integers.The solution set must not contain duplicate combinations.For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8, A solution set is: [  [1, 7],  [1, 2, 5],  [2, 6],  [1, 1, 6]]分析：此題在遞歸求解的過程中必須確保每個數字出現的次數不能超過實際出現的次數只需要修改for循環中i * candidate <= target中的條件為 i <= numToTimes[i] && i * candidate <= target輸入:7(數組元素個數) 8(目標值)10 1 2 7 6 1 5輸出:1 7,1 2 5,2 6,1 1 6關鍵：1 用回溯來做，如果目標值為0，就將結果壓入結果集。回溯適用于求解含有多個結果的集合回溯基本格式:嘗試某一數值遞歸清空嘗試的數值與可重復累加和的區別在于：可重復累加和一直嘗試當前值，直到目標值 < 當前候選值，則選取下一個候選值。  如果目標值>0,繼續嘗試下一個值，嘗試過后，彈出之前壓入的值	//如果目標變成0，說明得到結果，將結果加入結果集	if(0 == target)	{		results.push_back(path);		return;	}			//此種情況不可能	if(target < 0)	{		return;	}	int size = candidates.size();	for(int i = cur ; i < size ; i++)	{		//防止添加重復元素，如果當前元素和之前元素重復，就跳過		if(i > cur && candidates.at(i) == candidates.at(i-1))		{			continue;		}		path.push_back(candidates.at(i));		//嘗試下一個候選值		combineSum(candidates , target - candidates.at(i) , i + 1 , path , results);		//回溯		path.pop_back();	}2 求組合值為sum的解法 void combinationSum(std::vector<int> &candidates, int target, std::vector<std::vector<int> > &res, std::vector<int> &combination, int begin) {		if  (!target) {			res.push_back(combination);			return;		}        for (int i = begin; i != candidates.size() && target >= candidates[i]; ++i) {            combination.push_back(candidates[i]);            combinationSum(candidates, target - candidates[i], res, combination, i);            combination.pop_back();        }	}*/class Solution {public:	//嘗試用擺放來做，問題轉化為遞歸問題	void combineSum(vector<int>& candidates, int target , int cur , vector<int> path , vector< vector<int> >& results)	{		vector< vector<int> > totalResults;		if(candidates.empty())		{			return ;		}		//如果目標變成0，說明得到結果，將結果加入結果集		if(0 == target)		{			results.push_back(path);			return;		}				//此種情況不可能		if(target < 0)		{			return;		}		int size = candidates.size();		for(int i = cur ; i < size ; i++)		{			//防止添加重復元素，如果當前元素和之前元素重復，就跳過			if(i > cur && candidates.at(i) == candidates.at(i-1))			{				continue;			}			path.push_back(candidates.at(i));			//嘗試下一個候選值			combineSum(candidates , target - candidates.at(i) , i + 1 , path , results);			//回溯			path.pop_back();		}	}    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {		vector<vector<int>> results;		if(candidates.empty())		{			return results;		}        //必須確保候選值從大到小排序		sort(candidates.begin() , candidates.end());		vector<int> path;		combineSum(candidates, target , 0 , path , results);		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.combinationSum2(nums , target);		print(results);	}}int main(int argc , char* argv[]){	process();	getchar();	return 0;}