leetcode_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. 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] ]

        又是求和问题,博主的使用递归的方法,虽然给出正确结果,但是存在效率的问题:

class Solution {
public:
	vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
		vector<int> accumulate;
		std::sort(candidates.begin(), candidates.end());
		int index = 0;
		for (int i = 0; i < candidates.size(); i++){
			if (i && candidates.at(i - 1) == candidates.at(i)) continue;
			m_temp.clear();
			if (candidates.at(i) < target){
				m_temp.push_back(candidates.at(i));
				accumulate.assign(candidates.begin() + i + 1, candidates.end());
				combinationSum2Iter(accumulate, target - candidates.at(i));
				m_temp.pop_back();
			}
			else if (candidates.at(i) == target){
				m_temp.push_back(candidates.at(i));
				result.push_back(m_temp);
				m_temp.pop_back();
				break;
			}
			else{
				break;
			}
		}
		return result;
	}
protected:
	vector<int> m_temp;
	vector<vector<int>> result;
	void combinationSum2Iter(vector<int>& candidate, int target){
		vector<int> accumulate;
		for (int i = 0; i < candidate.size(); i++){
			if(i && candidate.at(i-1) == candidate.at(i)) continue;
			if (candidate.at(i) < target){
				m_temp.push_back(candidate.at(i));
				accumulate.assign(candidate.begin() + i + 1, candidate.end());
				combinationSum2Iter(accumulate, target - candidate.at(i));
				m_temp.pop_back();
			}
			else if (candidate.at(i) == target){
				m_temp.push_back(candidate.at(i));
				result.push_back(m_temp);
				m_temp.pop_back();
				break;
			}
			else{
				break;
			}
		}
	}
};

        代码比较长,下面总结一下递归法处理的思路:

1.先将数列进行排序,然后按照定和问题的思路来解决;

2.判断最小的数字是不是小于target_sum,如果小于target_sum,则这个数value入栈,右边的数字中需要和为target_sum – value,这样就编程了一个定和的递归问题。每次从中取出一个数,如果可以使和 小于 target,则继续取,如果 等于 target 则保存结果,如果大于target,则终止;

note:每次入栈,都对应一次出栈,递归法思路不好理,这一点一定要理解并且要作为基本常识。

3.由于遇到重复值需要跳过,则有下面这段经典代码:

		for (int i = 0; i < candidate.size(); i++){
			if(i && candidate.at(i-1) == candidate.at(i)) continue;

        这段代码怎样理解呢,我们假设输入序列是[1 1 1 3 1 3 6],target是6,我们会担心得不到[1 1 1 3]这样的结果,事实上,这种担心是不必要的。第一次进栈的是1,后面的序列为[1 1 1 3 3 6],第二次进栈的是1,剩下的是[1 1 3 3 6] …… ,得到[1 1 1 3]后,事实上我们已经将第一个数字为1的情况都考察过了。当我们再次选取第一个数字时,如果我们不跳过,也就是说假设我们没有if这句代码,我们会得到三个 [1 1 1 3] 这种重复的答案,这其中还有玄机,遍历第一个数字时的重复会增加一个,遍历第二个数字带来的重复也会增加一个,遍历第三个数字时的重复也会增加一个,最先发生的是最后一种情况,那么我们就能够理解代码中的这两处的if跳过了。

        OK,See You Next Chapter!

发表评论