leecode 解题总结：39. Combination Sum

#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, 分析:这是程序员面试金典的一道题目。求组成数的所有组合。应该是用递归做。之前是n分的硬币用25,10,5,1的硬币表示分别枚举i * denom <= total时，i从0到k的情况，然后递归做2 3 6 7此题应该也是用这种方式输入:4(数组元素个数) 7(目标值)2 3 6 74 62 3 6 72 72 6输出:7,2 2 36,3 3,2 2 2no result关键:1 前半部分求解结果，前半部分 与 后半部分结果 进行笛卡尔积 即为最终结果int curCandidate = candidates.at(curCandidateIndex);vector<vector<int>> results;//后半部分递归求解结果vector<int> result;//前半部分求解结果，前半部分 与 后半部分结果 进行笛卡尔积 即为最终结果for(int i = 0 ; i * curCandidate <= target ; i++){	result.clear();//清空上一次结果	for(int j = 0 ; j < i ; j++)	{		result.push_back(curCandidate);	}	results = combineSum(candidates , target -  i * curCandidate , curCandidateIndex + 1 );//得到多个结果需要和当前结果进行笛卡尔积拼接	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));	}	//如果当前直接等于结果集i * curCandidate = target,直接压入结果中	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;//后半部分递归求解结果		vector<int> result;//前半部分求解结果，前半部分 与 后半部分结果 进行笛卡尔积 即为最终结果		for(int i = 0 ; i * curCandidate <= target ; i++)		{			result.clear();//清空上一次结果			for(int j = 0 ; j < i ; j++)			{				result.push_back(curCandidate);			}			results = combineSum(candidates , target -  i * curCandidate , curCandidateIndex + 1 );//得到多个结果需要和当前结果进行笛卡尔积拼接			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));			}			//如果当前直接等于结果集i * curCandidate = target,直接压入结果中			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;}