# Generating subsets (combinations) using permutations

The idea of this algorithm is to use permutations of a boolean array to generate combinations.
The set bit(s) in a permutation can be used to mask the position(s) of an array containing the elements.
Note : c++ next__permutation function generates the next lexicographically greater permutation.

C++ : Generating combinations or subsets using permutations.

``````#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
typedef vector<vector<int>> VVI;

VVI GetCombinations (vector<int>& vec) {

int sz = vec.size();
vector<bool> buff(sz);
vector<vector<int>> combinations;

for (int r=0; r<=sz; r++) {

fill(buff.begin()+r, buff.end(), true);

do {
vector<int> comb;
for (int i=0; i<sz; i++) {
if (buff[i] == false) {
comb.push_back(vec[i]);
}
}
combinations.push_back(comb);
} while ( next_permutation(buff.begin(), buff.end()) );

fill(buff.begin(), buff.end(), false);
}

for (int i=0; i < combinations.size(); i++) {
cout << "( ";
for (int j=0; j < combinations[i].size(); j++) {
cout << combinations[i][j] << " ";
}
cout << ")" << endl;
}
return combinations;
}

int main() {

// This type of vector initialization needs support for c++11 in the compiler
vector<int> vec = { 1, 2, 3, 4};
vector<vector<int>> combinations = GetCombinations (vec);
return 0;
}
``````

Output

``````( )
( 1 )
( 2 )
( 3 )
( 4 )
( 1 2 )
( 1 3 )
( 1 4 )
( 2 3 )
( 2 4 )
( 3 4 )
( 1 2 3 )
( 1 2 4 )
( 1 3 4 )
( 2 3 4 )
( 1 2 3 4 )
``````