Given an array of unique integer elements, print all the subsets of the given array in lexicographical order [O(2^N) Solution].

gen_subsets.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define ull uint64_t

bool checkBit(int i, int j) { return (i>>j)&1; }

void generate_subsets(vector<vector<int>> &subsets, const vector<int> &arr) {
    int n = 1 << arr.size();    // 2^N => number of subsets
    int m = arr.size();         // N => original set size (named as 'm' because variables. LOL.)
    for(int i = 1; i < n; ++i) {
        vector<int> temp;
        for(int j = 0; j < m; ++j)
            if(checkBit(i, j))
                temp.push_back(arr[j]);
        subsets.push_back(temp);
    }
}

int main() {
    int t;  cin >> t;
    while(t--) {
        int n;  cin >> n;
        vector<int> arr(n);
        for(int i = 0; i < n; ++i)
            cin >> arr[i];
        sort(arr.begin(), arr.end());
        
        vector<vector<int>> subsets;
        generate_subsets(subsets, arr);
        
        // Optional step - custom sorting
        sort(subsets.begin(), subsets.end(), 
            [](const vector<int> &v1, const vector<int> &v2){
                for(ull i = 0; i < v1.size() && i < v2.size(); ++i) {
                    if(v1[i] == v2[i])
                        continue;
                    return v1 < v2;
                }
                return v1.size() < v2.size();
            });
        
        for(auto vec: subsets) {
            for(auto el: vec)
                cout << el << " ";
            cout << "\n";
        }
        
        if(t!=0) cout << "\n";
    }
}