77. Combinations
Description
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],
]
Analysis
实质上此题就是求subsets的变形，只需要控制好子集中的元素个数即可,代码如下:
code
class Solution {
private:
void backtracking(vector<vector<int>> & res,vector<int> & temp,int * num,int start,int k,int n){
if(temp.size()==k){
res.push_back(temp);
return;
}
for(int i=start;i<n;++i){
temp.push_back(num[i]);
backtracking(res,temp,num,i+1,k,n);
temp.pop_back();
}
}
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> res;
vector<int> temp;
int * array=new int[n];
for(int i=1;i<=n;++i)
array[i-1]=i;
backtracking(res,temp,array,0,k,n);
delete array;
return res;
}
};
此外，讨论区中还提供了另一种思路，但总感觉存在一种刻意针对此题要求进行拼凑的嫌疑，不能称为通解，下面将该种解法加以记录:
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
vector<vector<int>> result;
int i = 0;
vector<int> p(k, 0);
while (i >= 0) {
p[i]++;
if (p[i] > n) --i;
else if (i == k - 1) result.push_back(p);
else {
++i;
p[i] = p[i - 1];
}
}
return result;
}
};
For example, the (4, 2) test case yields:
Incremented element at index 0
[1, 0]
Moved index to the right, and copied the value from the left
[1, 1]
Incremented element at index 1
[1, 2]
Combination found!
Added [1, 2] as an answer!
Incremented element at index 1
[1, 3]
Combination found!
Added [1, 3] as an answer!
Incremented element at index 1
[1, 4]
Combination found!
Added [1, 4] as an answer!
Incremented element at index 1
[1, 5]
n exceeded at 1, moving index to the left
Incremented element at index 0
[2, 5]
Moved index to the right, and copied the value from the left
[2, 2]
Incremented element at index 1
[2, 3]
Combination found!
Added [2, 3] as an answer!
Incremented element at index 1
[2, 4]
Combination found!
Added [2, 4] as an answer!
Incremented element at index 1
[2, 5]
n exceeded at 1, moving index to the left
Incremented element at index 0
[3, 5]
Moved index to the right, and copied the value from the left
[3, 3]
Incremented element at index 1
[3, 4]
Combination found!
Added [3, 4] as an answer!
Incremented element at index 1
[3, 5]
n exceeded at 1, moving index to the left
Incremented element at index 0
[4, 5]
Moved index to the right, and copied the value from the left
[4, 4]
Incremented element at index 1
[4, 5]
n exceeded at 1, moving index to the left
Incremented element at index 0
[5, 5]
n exceeded at 0, moving index to the left
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]