Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,

If n = 4 and k = 2, a solution is:

[

 [2,4],

 [3,4],

 [2,3],

 [1,2],

 [1,3],

 [1,4],

]

做了好几个这种题了，就是 backtrack problem, １小时做出，但不容易，各种小毛病.

我的程序蠢蠢的建立了一个 vector<int> A;. 其实，只玩弄变量n就行了．

我犯的错误，如下：

start + 1, start++ 和 ++start

自己第一次写的代码是

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

	temp.push_back(A[i]);

	// 应把 start+1 改为 ++start, start 应该随 i 变化而变化

	backtrack(res, temp, A, len, start + 1);

	temp.pop_back();

}

e.g.

n = 4, k = 2

[1 2 3 4]

结果应为:        [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

我错误结果为:    [[1,2],[1,3],[1,4],[2,2],[2,3],[2,4],[3,2],[3,3],[3,4],[4,2],[4,3],[4,4]]

自个想法，自个代码：

vector<vector<int>> combine(int n, int k) {

	vector < vector<int> > res;

	vector<int> temp;

	vector<int> A;

	for (int i = 1; i <= n; i++)

		A.push_back(i);

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

	return res;

}

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

		const int len, int start) {

	if (temp.size() == len) {

		res.push_back(temp);

		return;

	}

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

		temp.push_back(A[i]);

		// start++;

		// 下面血淋淋地体现了

		// start + 1, start++ 和 ++start 的巨大不同了

		backtrack(res, temp, A, len, ++start);

		temp.pop_back();

	}

}