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

void print(std::vector<int> const &input){
      std::cout << '{';
      for (int i = 0; i < input.size(); i++) {
		std::cout << input.at(i);
        if (i < input.size() - 1)
          std::cout << ", ";
      }
      std::cout << '}';
}
void printMany(std::vector< std::vector<int> > const &input)
{
    std::cout << '{';
	for (int i = 0; i < input.size(); i++) {
      print(input.at(i));
      if (i < input.size() - 1)
        std::cout << ", ";
	}
    std::cout << '}';
    std::cout << '\n';
}
void printPairs(std::vector< std::vector<int> > const &input)
{
	for (int i = 0; i < input.size(); i+=2) {
      cout << '{';
      print(input.at(i));
      cout << ", ";
      print(input.at(i + 1));
      cout << "}\n";
	}
}
 
std::vector< std::vector<int> > f(std::vector<int> const &A, int i, const std::vector<int> &left, const std::vector<int> &right) {
  if (i == A.size() - 1 && right.empty())
    return std::vector< std::vector<int> >{left, std::vector<int> {A[i]}};
  if (i == A.size())
    return std::vector< std::vector<int> > {left, right};
 
  std::vector<int> _left{ left };
  _left.emplace_back(A[i]);
  std::vector< std::vector<int> > result = f(A, i + 1, _left, right);
  std::vector<int> _right{ right };
  _right.emplace_back(A[i]);
  std::vector< std::vector<int> > result1 = f(A, i + 1, left, _right);
  result.insert( result.end(), result1.begin(), result1.end() );
  return result;
}
 
std::vector< std::vector<int> > powerset(std::vector<int> const &A, const vector<int>& prefix = vector<int>(), int i = 0) {
  if (i == A.size())
    return std::vector< std::vector<int> > {prefix};

  std::vector<int> _prefix(prefix);
  _prefix.emplace_back(A[i]);
  std::vector< std::vector<int> > result = powerset(A, _prefix, i + 1);
  std::vector< std::vector<int> > result1 = powerset(A, prefix, i + 1);
  result.insert( result.end(), result1.begin(), result1.end() );
  return result;
}
 
int main() {
  std::vector<int> A{0, 1, 2};
  std::vector< std::vector<int> > ps = powerset(A);
  cout << "Powerset:\n";
  printMany(ps);
  cout << "\nResult:\n";
  for (int i=0; i<ps.size(); i++){
    if (ps.at(i).size() > 1){
      std::vector<int> left{ps.at(i)[0]};
      std::vector<int> right;
      printPairs(f(ps.at(i), 1, left, right));
    }
  }
  return 0;
}