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.

Combinations_Using_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 )


© 2019-2026 Algotree.org | All rights reserved.

This content is provided for educational purposes. Feel free to learn, practice, and share knowledge.
For questions or contributions, visit algotree.org

"There are two ways to write error-free programs; only the third one works. - Alan J. Perlis"