Leetcode: Combination Sum I && II

Combination Sum I

Given a set of candidate numbers (C) 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.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.
For example, given candidate set 2,3,6,7 and target 7,
A solution set is:
[7]
[2, 2, 3]

Solution:

Idea: this problem is not difficult to solve with backtrack.
Two key points: 1. The classic pattern of recursion: use two vectors to recursively save the result, one for the final result and the other for one possible solution. 2. remember to pop_back after adding to the solution to ret. 3. start from current index in the new recursion to get answers like [[1,1,1], [1,2]], input [1, 2], 3

	vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
	vector<vector<int> > ret;
	vector<int> retOne;
	std::sort(candidates.begin(), candidates.end());
	combinationSumRe(candidates, target, 0, candidates.size()-1, ret, retOne);
	return ret;
	}
	void combinationSumRe(vector<int> &cd, int target, int begin, int size, vector<vector<int>> &ret, vector<int> &retOne){
	for(int i = begin; i<= size; i++){
	if(cd[i]>target) return;
	if(cd[i] == target){
	retOne.push_back(cd[i]);
	ret.push_back(retOne);
	retOne.pop_back();
	return;
	}
	if(cd[i] < target){
	retOne.push_back(cd[i]);
	combinationSumRe(cd, target-cd[i], i,highId, ret, retOne);
	retOne.pop_back();
	}
	}
	}

view raw gistfile1.cpp hosted with ❤ by GitHub

Combination Sum II


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.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
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]

The difference lies that for next round start from i+1 as indicated in the following code:

	vector<vector<int> > combinationSum2(vector<int> &num, int target) {
	vector<vector<int> > ret;
	vector<int> solution;
	std::sort(num.begin(), num.end());
	combineSum(num, target, 0, num.size()-1, ret, solution);
	return ret;
	}
	void combineSum(vector<int> &cd, int target, int begin, int highId, vector<vector<int>> &ret, vector<int> &solution){
	int prev = cd[begin];
	for(int i = begin; i<= highId; i++){
	//skip duplicate letters in this round, but duplicate letters can be chosen in next round
	if(i!=begin){// to avoid two [1, 7]
	if(cd[i] == prev) continue;
	else prev= cd[i];
	}
	if(cd[i]>target) return;
	if(cd[i] == target)
	{
	solution.push_back(cd[i]);
	ret.push_back(solution);
	solution.pop_back();
	return;
	}
	if(cd[i] < target)
	{
	solution.push_back(cd[i]);
	//starting from i+1, different from I
	combineSum(cd, target-cd[i], i+1, highId, ret, solution);
	solution.pop_back();
	}
	}
	}

view raw gistfile1.cpp hosted with ❤ by GitHub