leetcode系列[四]----combinations

作者：代码牛仔

题目：

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

测试例子：

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

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

本题目给出两个整数，让在1-n中选择k个数，给出所有组合方式。这道题目就是一个组合问题。如果这个k是确定的给个循环就搞定问题，没有任何难度。然而难度就在于这个k的不确定，所以循环的层数不能确定，这样一来就不能用k次循环的遍历方式来解决问题。

递归可以解决这一问题，而任何递归算法都有相应的非递归的算法实现。所以我们分开讨论这两种算法。

递归实现：

原理：

递归描述：

如果是从集合A中取出1个数值，则递归结束

如果从集合A中取出的值大于一个，则取出一个之后，重构集合A记为B，递归执行（B，k-1);

代码：

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    vector<vector<int> > rs;
    vector<vector<int> > combine(int n, int k) {
        vector<int> nn;
        vector<int> surplus;
        for(int i=1;i<=n;i++){
            surplus.push_back(i);
        }
        com(nn,surplus,n,k);
        return rs;
    }
    void com(vector<int> newSur,vector<int> surplus,int n,int k){
    if(k==1){
        for(int i=0;i<surplus.size();i++){
            vector<int> temp = newSur;
            temp.push_back(surplus[i]);
            rs.push_back(temp);
        }
    }else{
        for(int i=0;i<=n-k;i++){
            vector<int> temp = newSur;
            temp.push_back(surplus[i]);
            vector<int> last;
            for(int j=i+1;j<surplus.size();j++){
                last.push_back(surplus[j]);
            }
            com(temp,last,last.size(),k-1);
        }
    }
    }
};
int main(){
cout<<"hello world"<<endl;
Solution sl;
vector<vector<int> > rs = sl.combine(4,2);
for(int i=0;i<rs.size();i++){
    cout<<"{";
    for(int j=0;j<rs[i].size();j++)
    {
        cout<<rs[i][j];
        if(j!=rs[i].size()-1)
          cout<<",";
    }

    cout<<"}"<<endl;
}
//getchar();
return 1;
}