[Leetcode] combinations 组合

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

题意：给定1...n个数，求出每k个数的组合情况。

思路：使用DFS。定义中间数组变量，每当其大小为k时，将其存入结果res；若不等于则继续调用。需要注意的是，组合是不讲究顺序的，所以下层的递归不用从头开始，只需从当前的下一个数字开始就行，另外，对第一层的选取，使用迭代，这样就可以考虑到所有情况，后面的从下层开始，用递归就好。这里有详细的解释。代码如下：

 1 class Solution {
 2 public:
 3     vector<vector<int> > combine(int n, int k) 
 4     {
 5         vector<vector<int>> res;
 6         vector<int> midRes;
 7         combineDFS(n,k,1,midRes,res);
 8         return res;    
 9     }
10 
11     void combineDFS(int n,int k,int beg,vector<int> &midRes,vector<vector<int>> &res)
12     {
13         if(midRes.size()==k)
14         {
15             res.push_back(midRes);
16         }
17         else
18         {
19             for(int i=beg;i<=n;++i)
20             {
21                 midRes.push_back(i);
22                 combineDFS(n,k,i+1,midRes,res);
23                 midRes.pop_back();
24             }
25         }
26     }
27 };

注：排列和组合的区别在于和顺序有关，如：[1,2]、[2,1]是两种不同的排列，却是相同的组合。