@jinxonik / UniLecs #189

brackets.cpp

#include <iostream>
#include <functional>

// Bracket balance search function, returns number of found balances
// count - number of brackets pairs
// callback - function called for found bracket balance (parameters: uint64_t - bracket balance bit mask, int - number of bracket pairs)
//   bit balance: lower bit (number 0) - first bracket, higher bit (number count-1) - last bracket: 0 - opened, 1 - closed
// list - bracket balance bit mask (used in recursion, leave zero on root call)
// opened, closed - number of opened/closed brackets in list (used in recursion, leave zero on root call)
uint64_t brackets(int count, std::function<void(uint64_t, int)> callback, uint64_t list = 0, int opened = 0, int closed = 0)
{
  if (opened + closed == 2 * count) {
    callback(list, count);
    return 1;
  }
  uint64_t total = 0;
  if (opened < count) { total += brackets(count, callback, list << 1, opened+1, closed); }
  if (opened > closed) { total += brackets(count, callback, (list << 1) + 1, opened, closed+1); }
  return total;
}

void print(uint64_t list, int count)
{
  for (uint64_t mask = 1 << (count * 2 - 1); mask > 0; mask >>= 1) {
    std::cout << (list & mask ? ')' : '(');
  }
  std::cout << '\n';
}

int main()
{
  std::cout << "Enter count (1..32): ";
  int count;
  std::cin >> count;
  if (count < 1 || count > 32) {
    std::cout << "Wrong number!\n";
    return 1;
  }

  std::function<void(uint64_t, int)> callback;
  if (count <= 8) { callback = print; } else { callback = [](uint64_t, int){}; }
  int total = brackets(count, callback);
  std::cout << "Total = " << total;

  return 0;
}