39. Combination Sum(medium, backtrack 的经典应用, 重要)

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 the 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,

A solution set is:

[

 [7],

 [2, 2, 3]

]

本题是 backtrack(回溯法) 的经典应用.通过本题，仔细观察 backtrack 基本框架，并感受其应用.

另外, subset 的题目也用 backtrack 方法.

人家想法，自个代码:

cpp 副产品： v.pop_back(); 弹出队尾元素.
要注意的是: 下面代码中 backtrack 方法中的 res, temp, A, 尤其是 temp, 他们都分别指向对应的一个对象，无论 backtrack 方法被嵌套地调用多少次！

// backtrace method

vector<vector<int>> combinationSum(vector<int>& A, int ta) {

	sort(A.begin(), A.end());

	vector < vector<int> > res;

	vector<int> temp;

	backtrack(res, temp, A, ta, 0);

	return res;

}

void backtrack(vector<vector<int> >& res, vector<int>& temp, vector<int>& A,

		int remain, int start) {

	if (remain < 0)

		return;

	else if (remain == 0) {

		res.push_back(temp);

		return;

	} else {

		for (int i = start; i < A.size(); i++) {

			temp.push_back(A[i]);

			// not i + 1, because A[i] might be reused.

			backtrack(res, temp, A, remain - A[i], i);

			temp.pop_back();

		}

		return;

	}

}

巴特西

39. Combination Sum(medium, backtrack 的经典应用, 重要)

最新文章

热门文章