22_generate_parentheses

dz / leetcode / 22_generate_parentheses

Summary

22. Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Node Tree

• URL
• editorial
  • backtracking
    • valid_only_equal_left_right
  • brute_force_with_queue
  • divide_and_conquer
• intuition
  • recursion
    • dynamic_programming
      • divide_and_conquer
  • always_same_size
  • brute_force
  • dynamic_programming
    • divide_and_conquer
  • finding_patterns
    • always_same_size
    • first_entry_always_L
    • n_1
      • n_2
    • n_2
    • n_3
      • recursion
        • dynamic_programming
          • divide_and_conquer
      • n_1
        • n_2
  • first_entry_always_L
  • generate_first_half

Nodes

URL
content	URL
hyperlink	https://leetcode.com/problems/generate-parentheses/

intuition
content	Firstly, Parentheses are hard to read. Choosing different values for left/right parentheses could make it easier to see patterns. Secondly, yes I think something could be figured out using patterns. Pretty sure larger numbers of parentheses can be derived from smaller patterns. Dynamic programming? The size of N goes from 1 to 8, so that would suggest a space-intensive solution.
children	recursion, always_same_size, brute_force, dynamic_programming (trying to come up with a ), finding_patterns, first_entry_always_L, generate_first_half

finding_patterns
content	Going to find some patterns, using L for "left paren" (, and R for "right paren" ).
children	always_same_size, first_entry_always_L, n_1, n_2, n_3 (translating given example)
parents	intuition

n_3
content	When n=3, the combinations are LLLRRR, LLRLRR, LLRRLR, LRLLRR, LRLRLR
children	recursion, n_1 (next)
parents	finding_patterns

n_1
content	There is only one combination: LR
children	n_2 (next)
parents	n_3, finding_patterns

n_2
content	n=2, LRLR, LLRR
parents	n_1, finding_patterns

always_same_size
content	Each sequence is always the same size of 2N. There is an equal number of left and right parentheses.
parents	intuition, finding_patterns

brute_force
content	There are 2^N total combinations to choose, a maximum of 256 iterations. You could produce every combination, some way of checking if it is properly closed, then adding it to an array if it is.
parents	intuition

first_entry_always_L
content	The first entry always has to be left (L), which would imply that the last item is always right (R).
parents	intuition, finding_patterns

generate_first_half
content	I wonder if there's any effeciency involved in generating the first half of sequence, then working with the other half?
parents	intuition

recursion
content	It seems like this could be a solution you could express recursively. In the example, it was very clear that at the end there were 3 small pairs LRLRLR, and at the those pairs were nested.
children	dynamic_programming (follow-up, inspired by seeing smaller things grow into)
parents	intuition, n_3

dynamic_programming
content	larger things Oh, I see how things could be broken up into smaller problems. With a function GP(n), and the operator GP(x)*GP(y) concatenates all the combinations for inside of GP(x) and GP(y) with X followed by Y. would can see how when N=0, the output is [] when N=1, the output is [LR], or [L*GP(0)*R, GP(0)*LR, LR*GP(0)]. when N=2, the combinations are [GP(1)*GP(1),LGP(1)R]. When N=3, the combinations are all of 2 plus an extra pair: GP(2)*LR, LR*GP(2), L*GP(2)*R. Which can be generalized as [GP(N-1)*LR, LR*GP(N-1), LGP(N-1)]. This notation produces duplicates though. I think it's close to a more elegant solution than brute force.
children	divide_and_conquer (similar line of thinking)
parents	intuition, recursion

editorial
content	editorial
children	backtracking, brute_force_with_queue, divide_and_conquer

brute_force_with_queue
content	The brute force version uses a queue. I don't have much practical experience working with queue data structures, so it'd be good to write this one out a language that has them trivially. I did however, get the gist of this, just not how to implement it.
parents	editorial

backtracking
content	Use backtracking to generate only valid strings. Left/right counts are used to check if valid.
children	valid_only_equal_left_right
parents	editorial

valid_only_equal_left_right
content	Is it safe to say that if a sequence has an equal number of left/right parens, it is guaranteed to be balanced? That'd be an interesting one to prove.
parents	backtracking

divide_and_conquer
content	The problem of generating all well-formed parens of length 2n can be decomposed into smaller subproblems of generating valid strings of smaller lengths. I was on the right track, but couldn't get past the duplicate calculations because I wasn't setting it up right.
parents	editorial, dynamic_programming