number of balanced bracket subsequences

// I can't tell you what it really is,
// I can only tell you what it feels like.
#include "bits/stdc++.h"
using namespace std;

const int N = 100;

int dp[N][N], n;
char s[N];

int go(int ind, int bal) {
  if (bal < 0) return 0;
  if (!ind and !bal) return 1;
  if (ind < 1) return 0;
  if (dp[ind][bal] != -1) return dp[ind][bal];
  int x = go(ind-1, bal + (s[ind] == '(' ? -1 : 1));
  x += go(ind-1, bal);
  return x;
}

signed main() {
  memset(dp, -1, sizeof dp);
  cin >> s+1;
  n = strlen(s+1);
  // cout << (s+1) << '\n';
  cout << go(n,0);
  return 0;
}
// 1). Try forming/rearranging the equations if any
// 2). If problem asks to count, try counting in reverse(it can be easier sometimes)