Permutation of words that have matched parentheses

Question

Let $L$ denote the (context-free) language of matched parentheses over the alphabet $\Sigma$. Consider the following problem:

Input: words $x_1,\dots,x_n \in \Sigma^*$
Question: does there exist a permutation $\sigma$ of $\{1,\dots,n\}$ such that $x_{\sigma(1)} x_{\sigma(2)} \cdots x_{\sigma(n)} \in L$?

What is the complexity of this problem? Can it be solved in polynomial time? Is it NP-hard?

It "smells" like something that might be NP-hard. But perhaps there is a way to reduce this to the route inspection problem (which has a polynomial-time algorithm), perhaps by treating each $x_i$ as an edge in some graph, or something?

---

Motivation: This is inspired by a question about permutations of lines of code, but my main interest is just curiousity.

Related:

• Time complexity of a problem inspired by palindromes claims to show that the problem is NP-hard when $L$ is the language of palindromes, a different context-free language (though I don't understand the proof).
• Word tiling, where you must use each tile exactly once considers the problem where $L=\{y\}$ where $y \in \Sigma^*$ is a single word specified as part of the input, and the answers show this is NP-hard too.