The sorting is useless. My other solution (with it removed) runs faster. Wish I could delete this one!

This one was a real blast, thank you. Now I can get on with my life :-)

I was getting correct answers but struggling with the 12 second timeout during the random tests, so I knew I was close... but my solution was messy.

A complete change in approach made the code much faster and much more readable... very satisfying when that happens. Bring on the 8x8!

I had a really hard time understanding the rules, like several people in the comments, because you express the problem in terms of adding braces.

Could I suggest that you phrase the problem something like:
"Varying the order of evaluation, how many distinct expression trees evaluate to true?"

This is unambiguous and answers questions like:
"is t|t|t distinct from (t|t)|t and t|(t|t) ?"
(answer: no, it's either one or the other)

Even once you understand the problem, I think it's a little hard for 3 kyu. I really enjoyed it anyway, so thanks.