LeetCode Q77: 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],
]

Solution 1: Recusion

	class Solution {
	public:
	vector<vector<int>> helper(int s, int e, int k){
	vector<vector<int> > res;
	if(k==1){
	for(int i=s; i<=e; i++){
	vector<int> r(1, i);
	res.push_back(r);
	}
	return res;
	}
	for(int i=e; i>=s; i--){
	vector<vector<int> > tmp=helper(s, i-1, k-1);
	for(int j=0; j<tmp.size(); j++){
	vector<int> t=tmp[j];
	t.push_back(i);
	res.push_back(t);
	}
	}
	return res;
	}
	vector<vector<int>> combine(int n, int k) {
	vector<vector<int> > res;
	if(n<=0||k<=0)
	return res;
	res=helper(1, n, k);
	}
	};

view raw Q77Combinations.cpp hosted with ❤ by GitHub

Solution 2: Non-recursion

	vector<vector<int>> combine(int n, int k) {
	vector<vector<int> > res;
	vector<int> p(k, 0);
	int i=0;
	while(true){
	if(i<0)
	break;
	p[i]++;
	if(p[i]>n){
	i--;
	continue;
	}
	if(i==k-1){
	res.push_back(p);
	continue;
	}
	i++;
	p[i]=p[i-1];
	}
	return res;
	}

view raw Q77-2.cpp hosted with ❤ by GitHub

Round 2 solution

	class Solution {
	public:
	void helper(vector<vector<int> >& res, vector<int>& curRes, int n, int k, int curK){
	if(curK==k){
	res.push_back(curRes);
	return;
	}
	for(int i=curRes.back()+1; i<=n; i++){
	curRes.push_back(i);
	helper(res, curRes, n, k, curK+1);
	curRes.pop_back();
	}
	}
	vector<vector<int>> combine(int n, int k) {
	vector<vector<int> > res;
	vector<int> curRes;
	for(int i=1; i<=n-k+1; i++){
	curRes.push_back(i);
	helper(res, curRes, n, k, 1);
	curRes.pop_back();
	}
	return res;
	}
	};

view raw Q77.cpp hosted with ❤ by GitHub