Combinations Solutions in C++

// Source : https://oj.leetcode.com/problems/combinations/
// Author : Hao Chen
// Date   : 2014-07-03



#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void getCombination(int n, int k, vector<int>& solution, vector< vector<int> >& result );
vector<vector<int> > combine1(int n, int k); 
vector<vector<int> > combine2(int n, int k);

vector<vector<int> > combine(int n, int k) {
    if (random()%2){
        cout << "recusive method!" << endl;
        return combine1(n, k);
    }
    cout << "non-recusive method!" << endl;
    return combine2(n, k);
}

vector<vector<int> > combine1(int n, int k) {
    vector<vector<int> > result;
    vector<int> solution;
    getCombination(n, k, solution, result);
    return result;
}

void getCombination(int n, int k, vector<int>& solution, vector< vector<int> >& result ){
    if (k==0){
        //sort to meet LeetCode requirement
        vector<int> v = solution;
        sort(v.begin(), v.end());
        result.push_back(v);
        return;
    }
    for(int i=n; i>0; i--){
        solution.push_back(i);
        getCombination(i-1, k-1, solution, result);
        solution.pop_back();
    }
}

vector<vector<int> > combine2(int n, int k) {
    
    vector<vector<int> > result;
    vector<int> d;
    for (int i=0; i<n; i++){
        d.push_back( (i<k) ? 1 : 0 );
    }

    //1) from the left, find the [1,0] pattern, change it to [0,1]
    //2) move all of the 1 before the pattern to the most left side
    //3) check all of 1 move to the right
    while(1){
        vector<int> v;
        for(int x=0; x<n; x++){
            if (d[x]) v.push_back(x+1);
        }
        result.push_back(v);
        //step 1), find [1,0] pattern
        int i;
        bool found = false;
        int ones =0;
        for(i=0; i<n-1; i++){
            
            if (d[i]==1 && d[i+1]==0){
                d[i]=0; d[i+1]=1;
                found = true;
                //step 2) move all of right 1 to the most left side
                for (int j=0; j<i; j++){
                    d[j]=( ones > 0 ) ? 1 : 0;
                    ones--;
                }
                break; 
            } 
            if (d[i]==1) ones++;
        }
        if (!found){
            break;
        }
        
    }
    return result;
    
}




void printResult(vector<vector<int> >& result)
{
    for(int i=0; i<result.size(); i++){
        cout << "{";
        for(int j=0; j<result[i].size(); j++){
            cout << " " << result[i][j];
        }
        cout << " }" <<endl;
    }
}

int main(int argc, char** argv)
{
    srand(time(NULL));

    int n = 4, k =2;
    if (argc>2){
        n = atoi(argv[1]);
        k = atoi(argv[2]);
    }
    vector<vector<int> > r = combine(n, k);
    printResult(r);
}

#include <vector> 
#include <functional>

using std::vector; using std::function;

class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        vector<vector<int>> retv;
        vector<int> vec(k);
        function<void(int, int, int)> combine = [&](int i, int n, int k) {
            for (int j=k-1; i>0; j ? combine(i, n, j) : retv.push_back(vec))
                vec[j] = i--;
        };
        combine(n,n,k);
        return retv;
    }
};

/// Source : https://leetcode.com/problems/combinations/description/
/// Author : liuyubobobo
/// Time   : 2017-11-18

#include <iostream>
#include <vector>

using namespace std;


/// Naive Recursive
/// Time Complexity: O(k * C(n, k))
/// Space Complexity: O(k)
class Solution {

private:
    vector<vector<int>> res;

    void generateCombinations(int n, int k, int start, vector<int> &c){

        if(c.size() == k){
            res.push_back(c);
            return;
        }

        for(int i = start ; i <= n ; i ++){
            c.push_back( i );
            generateCombinations(n, k, i + 1, c);
            c.pop_back();
        }

        return;
    }

public:
    vector<vector<int>> combine(int n, int k) {

        res.clear();
        if( n <= 0 || k <= 0 || k > n )
            return res;

        vector<int> c;
        generateCombinations(n, k, 1, c);

        return res;
    }
};


void print_vec(const vector<int>& vec){

    for(int e: vec)
        cout << e << " ";
    cout << endl;
}

int main() {

    vector<vector<int>> res = Solution().combine(4,2);
    for( int i = 0 ; i < res.size() ; i ++ )
        print_vec(res[i]);
    return 0;
}

/// Source : https://leetcode.com/problems/combinations/description/
/// Author : liuyubobobo
/// Time   : 2017-11-18

#include <iostream>
#include <vector>

using namespace std;


/// Naive Recursive Optimized
/// Time Complexity: O(k * C(n, k))
/// Space Complexity: O(k)
class Solution {

private:
    vector<vector<int>> res;

    void generateCombinations(int n, int k, int start, vector<int> &c){

        if(c.size() == k){
            res.push_back(c);
            return;
        }

        // i will at most be n - (k - c.size()) + 1
        for(int i = start; i <= n - (k - c.size()) + 1 ; i ++){
            c.push_back(i);
            generateCombinations(n, k, i + 1 ,c);
            c.pop_back();
        }

        return;
    }

public:
    vector<vector<int>> combine(int n, int k) {

        res.clear();
        if(n <= 0 || k <= 0 || k > n)
            return res;

        vector<int> c;
        generateCombinations(n, k, 1, c);

        return res;
    }
};


void print_vec(const vector<int>& vec){

    for(int e: vec)
        cout << e << " ";
    cout << endl;
}

int main() {

    vector<vector<int>> res = Solution().combine(4,2);
    for( int i = 0 ; i < res.size() ; i ++ )
        print_vec(res[i]);
    return 0;
}

/// Source : https://leetcode.com/problems/combinations/description/
/// Author : liuyubobobo
/// Time   : 2019-03-29

#include <iostream>
#include <vector>

using namespace std;


/// Using bit mask
/// Time Complexity: O(2^n * n)
/// Space Complexity: O(1)
class Solution {

public:
    vector<vector<int>> combine(int n, int k) {

        vector<vector<int>> res;

        int LIMIT = (1 << n);
        for(int i = 0; i < LIMIT; i ++){

            vector<int> tres = get_vector(i);
            if(tres.size() == k) res.push_back(tres);
        }
        return res;
    }

private:
    vector<int> get_vector(int num){

        vector<int> res;
        int i = 1;
        while(num){
            if(num % 2) res.push_back(i);
            i ++, num /= 2;
        }
        return res;
    }
};


void print_vec(const vector<int>& vec){

    for(int e: vec)
        cout << e << " ";
    cout << endl;
}

int main() {

    vector<vector<int>> res = Solution().combine(4,2);
    for( int i = 0 ; i < res.size() ; i ++ )
        print_vec(res[i]);
    return 0;
}

/// Source : https://leetcode.com/problems/combinations/description/
/// Author : liuyubobobo
/// Time   : 2019-03-29

#include <iostream>
#include <vector>

using namespace std;


/// Get all the combinations in place
/// Find the first non-saturated element and increase it
///
/// Time Complexity: O(k * C(n, k))
/// Space Complexity: O(1)
class Solution {

public:
    vector<vector<int>> combine(int n, int k) {

        vector<vector<int>> res;

        vector<int> c;
        for(int i = 1; i <= k; i ++)
            c.push_back(i);
//        Solution::print_vec(c);
        res.push_back(c);

        while(c[0] != n - k + 1){

            if(c.back() != n) c.back() ++;
            else{
                int i;
                for(i = k - 1; i >= 0; i --)
                    if(c[i] != i + n - k + 1){
                        c[i] ++;
                        for(int j = i + 1; j < k; j ++)
                            c[j] = c[j - 1] + 1;
                        break;
                    }
            }
//            Solution::print_vec(c);
            res.push_back(vector<int>(c.begin(), c.begin() + k));
        }
        return res;
    }

    static void print_vec(const vector<int>& vec){

        for(int e: vec)
            cout << e << " ";
        cout << endl;
    }
};


int main() {

    vector<vector<int>> res = Solution().combine(4,3);
    for( int i = 0 ; i < res.size() ; i ++ )
        Solution::print_vec(res[i]);

    return 0;
}

/// Source : https://leetcode.com/problems/combinations/description/
/// Author : liuyubobobo
/// Time   : 2019-03-29

#include <iostream>
#include <vector>

using namespace std;


/// Get all the combinations in place
/// find the first j which nums[j] + 1 != nums[j + 1] and increase nums[j]
/// See here for details: https://leetcode.com/problems/combinations/solution/
///
/// Time Complexity: O(k * C(n, k))
/// Space Complexity: O(1)
class Solution {

public:
    vector<vector<int>> combine(int n, int k) {

        vector<vector<int>> res;

        vector<int> c;
        for(int i = 1; i <= k; i ++)
            c.push_back(i);
        c.push_back(n + 1);

        int j = 0;
        while(j < k){

            res.push_back(vector<int>(c.begin(), c.begin() + k));

            for(j = 0; j < k && c[j] + 1 == c[j + 1]; j ++)
                c[j] = j + 1;

            c[j] ++;
        }
        return res;
    }
};


void print_vec(const vector<int>& vec){

    for(int e: vec)
        cout << e << " ";
    cout << endl;
}

int main() {

    vector<vector<int>> res = Solution().combine(4,3);
    for( int i = 0 ; i < res.size() ; i ++ )
        print_vec(res[i]);
    return 0;
}