#include <bitset>

class Combination {
public:
    
    // Throw exception when either m or n is invalid.
    // m should not be greater than 64, and n of course should be less than m.
    void init(int m, int n) {
        if (m > 64 || m < 0 || n > m || n <0) throw "Invalid m or n.";
        this->m = m;
        bits = (1ul << n) - 1;
        max = (1ul << m) - 1;
        hasNextCombination = true;
    }
    
    // Generate next combination.
    // Return false if there're no more combinations.
    // Result is store in argument "out".
    bool nextCombination(vector<int>& out) {
        out.clear();
        if (hasNextCombination) {
            bitset<64> bitset(bits);
            for (int i = 0; i < m; i ++) {
                if (bitset[i]) out.push_back(i);
            }
            hasNextCombination = next_combination(bits) && bits <= max;
            return true;
        } else {
            return false;
        }

    }

private:
    int m;
    unsigned long bits;
    unsigned long max;
    bool hasNextCombination;
    
    // Credit to https://www.wikiwand.com/en/Combination
    bool next_combination(unsigned long& x) // assume x has form x'01^a10^b in binary
    {
        unsigned long u = x & -x; // extract rightmost bit 1; u =  0'00^a10^b
        unsigned long v = u + x; // set last non-trailing bit 0, and clear to the right; v=x'10^a00^b
        if (v==0) // then overflow in v, or x==0
            return false; // signal that next k-combination cannot be represented
        x = v +(((v^x)/u)>>2); // v^x = 0'11^a10^b, (v^x)/u = 0'0^b1^{a+2}, and x ← x'100^b1^a
        return true; // successful completion
    }
};

// Usage:
int main() {
    Combination combination;
    vector<int> data {1, 2, 3, 4};
    // Select combination of 3 element from data;
    combination.init(data.size(), 3);
    vector<int> result;
    while (combination.nextCombination(result)) {
        for (auto index : result) {
            cout << data[index] << " ";
        }
        cout << "\n";
    }
    // output:
    // 1 2 3
    // 1 2 4
    // 1 3 4
    // 2 3 4
}