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：递归解法，仿照根据LeetCode:Subsets 的算法1解法，每一个元素有两种状态：选择、不选择

 1 class Solution {
 2 public:
 3     vector<vector<int> > combine(int n, int k) {
 4         vector<vector<int> >res;
 5         vector<int>tmpres;
 6         helper(1,n,k,tmpres,res);
 7         return res;
 8     }
 9     
10     //从[left, right]范围内选取k个数，tmpres是一个临时组合
11     void helper(int left, int right, int k, vector<int> &tmpres, vector<vector<int> >&res)
12     {
13         if(right-left+1 < k)return;
14         if(k == 0)
15         {
16             res.push_back(tmpres);
17             return;
18         }
19         //选择left
20         tmpres.push_back(left);
21         helper(left+1, right, k-1, tmpres, res);
22         tmpres.pop_back();
23         //不选择left
24         helper(left+1, right, k, tmpres, res);
25     }
26 };

算法2：还有另一种递归的思路，以一个例子来解释这种方法，假如要在6个元素（1,2,3,4,5,6）中选取3个元素，（我们对选取的元素组合加一个限制：选取的3个元素的相对顺序和他们在原始数组中的顺序一致，对于组合问题，这个条件对结果没有影响）：

选取第一个元素：第一个元素只能从[1,2,3,4]中选取，因为如果第一个元素选择5或者6，就不能保证选取的3个元素组合满则上面的限制
假设第一个元素选取的是2，那么第二个元素只能从[3,4,5]中选取，原因同上
假设第二个元素选取的是4，那么第三个元素只能从[5,6]中选取，原因同上

 1 class Solution {
 2 public:
 3     vector<vector<int> > combine(int n, int k) {
 4         vector<vector<int> >res;
 5         vector<int>tmpres;
 6         helper(1,n,k,tmpres,res);
 7         return res;
 8     }
 9     
10     //从[left, right]范围内选取k个数，tmpres是一个临时组合
11     void helper(int left, int right, int k, vector<int> &tmpres, vector<vector<int> >&res)
12     {
13         if(k == 0)
14         {
15             res.push_back(tmpres);
16             return;
17         }
18         for(int i = left; i <= right-k+1; i++)
19         {
20             tmpres.push_back(i);
21             helper(i+1, right, k-1, tmpres, res);
22             tmpres.pop_back();
23         }
24     }
25 };

算法3：非递归的实现。回想一下前面求集合的子集问题，这两个问题都是某个元素而言，选择或者不选择。只是组合问题对子集的大小限制为k，因此我们可以在求子集问题的基础上有如下代码（具体可以先参考子集问题的博文）：本文地址

class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int> >res;
        vector<vector<int> >vec(1);
        for(int i = 1; i <= n; i++)
        {
            int len = vec.size();
            vector<int> tmp;
            for(int j = 0; j < len; j++)
            {
                tmp = vec[j];
                tmp.push_back(i);
                if(tmp.size() == k)res.push_back(tmp);
                else vec.push_back(tmp);
            }
        }
        return res;
    }
};

算法4：基于位操作，这里我们主要借助一个二进制操作“求最小的、比x大的整数M，使得M与x的二进制表示中有相同数目的1”，如果这个操作已知，那么我们可以设置一个初始整数bit，bit的低位第1~k个二进制位为1，其余二进制位为0，bit的二进制表示一种组合，然后调用上述操作求得下一个bit，bit的最大值为：bit从低位起第n-k+1~n位等于1，其余位等于0，即(1<<n) - (1<<(n-k)，关于这个方法具体可以参考给力！高效！易懂！位运算求组合

 1 class Solution {
 2 public:
 3     vector<vector<int> > combine(int n, int k) {
 4         vector<vector<int> >res;
 5         vector<int>tmpres;
 6         for(int bit = (1<<k) - 1; bit <= (1<<n) - (1<<(n-k)); bit = NextN(bit))//注意bit的最大值为(1<<n) - (1<<(n-k)即选择n的前k个
 7         {
 8             tmpres.clear();
 9             for(int i = 0; i < n; i++)
10             {
11                 if(bit & (1<<i))
12                     tmpres.push_back(i+1);
13             }
14             res.push_back(tmpres);
15         }
16         return res;
17     }
18     //返回最小的、比N大的整数M，使得M与N的二进制表示中有相同数目的1
19     int NextN(int N) 
20     { 
21         int x = N&(-N);      
22         int t = N+x; 
23         return t | ((N^t)/x)>>2; 
24     }
25 };

算法5：算法之排列与组合算法这篇文章中还介绍了另一种基于二进制的做法，描述如下：

本程序的思路是开一个数组，其下标表示1到n个数，数组元素的值为1表示其代表的数被选中，为0则没选中。

首先初始化，将数组前n个元素置1，表示第一个组合为前n个数。

然后从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为“01”组合，同时将其左边的所有“1”全部移动到数组的最左端。

当第一个“1”移动到数组的n-m的位置，即n个“1”全部移动到最右端时，就得到了最后一个组合。

例如求5中选3的组合：

1 1 0 0 //1,2,3
 
1 0 1 0 //1,2,4
 
0 1 1 0 //1,3,4
 
1 1 1 0 //2,3,4
 
1 0 0 1 //1,2,5
 
0 1 0 1 //1,3,5
 
1 1 0 1 //2,3,5
 
0 0 1 1 //1,4,5
 
1 0 1 1 //2,4,5
 
0 1 1 1 //3,4,5