i'm back!!!11!!
and this time i'm not gonna do some cf problem, it's actually going to one from codewars
the problem itself is actually kinda simple
it gives you n, and asks you to find the element at the ith index in a sorted list of all balanced parenthesis
so like if n was 3, the list would be this:
and you have to find whatever element at whatever position it asks you to find
i was stuck on this problem for like 2 whole days then i realized it was way simpler than i thought
so let's build the parenthesis one by one, using
bal_parens(3, 2) as an example
we start with an empty string with an opening parenthesis (since it has to start w/ one):
now, how do we know whether we should add a `)` or another `(`?
well, notice that if we add a `)`, we've limited ourselves to only being able to
make the last 2 elements of the list
(remember that the list is sorted in alphabetical order, so we can make this assumption)
we want the 3rd element, so it's obvious why we can't add a `)`- we have to add a `(`
NOTE! that if we had wanted the second half of the list, we'd have to subtract 3 (the size of the first half) from our target index to maintain the accuracy of the value
now onto the next choice- another `(` or a `)`?
we do the calculations again
do we want the first element, or the last 2 elements?
we def want the last 2, so let's go with those, subtracting 1 from our index
and continuing this calculation, we end up with `(()())`, which is the correct answer
now we just need a way to quickly compute how many ways there are to compute the # of ways to complete a set of
parenthesis given the # of opening parenthesis and the # of closing parenthesis
it's a good thing this can be doable with simple dp-
let complete_ways[o][c] be the # of ways to complete a par string
given `o` opening & `c` closing parenthesis
this would be the table if the total # of parentheses was 3
```py [[5, 0, 0, 0], [5, 2, 0, 0], [3, 2, 1, 0], [1, 1, 1, 1]] ```
we have a base case of complete_ways[par_amt][par_amt] = 1,
and the recursion relation is p simple as well:
complete_ways[o][c] = complete_ways[o + 1][c] + complete_ways[o][c + 1](given that the previous indices are defined, of course)
but without further ado, here's my code
```py from typing import Optional from math import comb from functools import lru_cache @lru_cache def balanced_paren_num(par_amt: int) -> int: assert par_amt >= 0 # formula from https://en.wikipedia.org/wiki/Catalan_number return comb(2 * par_amt, par_amt) // (par_amt + 1) def balanced_parens(par_amt: int, ind: int) -> Optional[str]: assert par_amt >= 0 total = balanced_paren_num(par_amt) # total number of balanced parenthesis # simple bounds checking if not 0 <= ind < total or par_amt < 0: return None if par_amt in [0, 1]: # idk if my function can handle these cases return '' if par_amt == 0 else '()' # this[o][c] = ways to complete given o opening parenthesis & c closing parenthesis complete_ways = [[0 for _ in range(par_amt + 1)] for _ in range(par_amt + 1)] complete_ways[par_amt][par_amt] = 1 for o in range(par_amt, -1, -1): for c in range(o, -1, -1): if o + 1 <= par_amt: complete_ways[o][c] += complete_ways[o + 1][c] if c + 1 <= par_amt: complete_ways[o][c] += complete_ways[o][c + 1] def actual_calc(curr_str: str, o_amt: int, c_amt: int, rel_ind: int) -> str: if o_amt == par_amt: return curr_str + ')' * (par_amt - c_amt) # adding the o comes before adding the c add_o = complete_ways[o_amt + 1][c_amt] if rel_ind < add_o: return actual_calc(curr_str + '(', o_amt + 1, c_amt, rel_ind) return actual_calc(curr_str + ')', o_amt, c_amt + 1, rel_ind - add_o) return actual_calc('', 0, 0, ind) print(balanced_parens(2, 0)) # should output (()) print(balanced_parens(2, 1)) # should output ()() print(balanced_parens(3, 3)) # should output ()(()) print(balanced_parens(3, 5)) # should output None ```