问题:
Given two integers n and k, return all possible combinations ofk 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],
]
解答思路:
首先我们从n个数中取一个数,然后剩下的n-1个数又构成一个Combinations问题:从n-1(除去刚选择的那个数)个数中选择k个数的组合。所以这是一个递归问题。
参考代码:
class Solution
{
private:
//n为生成范围的上限,k为组合中包含元素的个数,start为递归进行中的当前组合元素个数,item为当前组合结果,result为最终组合结果
void combine(int n, int k, int start, vector<int> &item, vector<vector<int>> &result)
{
if (item.size() == k)
{
result.push_back(item);
return;
}
for (int i = start; i <= n; i++)
{
item.push_back(i);//取出第一个元素加入item中,即第一个位置放置i
combine(n, k, i + 1, item, result);//剩下k-1个位置进行迭代计算
item.pop_back();//执行完以后将当前的元素弹出,重新进行一下一轮运算
}
}
public:
vector<vector<int>> combine(int n, int k)
{
vector<vector<int>> result;
vector<int> item;
if (n >= k && k > 0)
{
combine(n, k, 1, item, result);
}
return result;
}
};