Is there any trick to quickly get the sequence of inner elements given their corresponding sum? (e.g. given the sums 5 4 3, results in 2, 3; 3, 1; 1, 2)

Previously without such method, my implementation uses permutations to generate inner sequence which is very slow. For it runs like forever.

EDIT: Got a function to generate the inner sequence. This function starts with picking (from the chosen inner elements) two valid elements according to their sum, and use them as the first two elements of the inner sequence, and then all the rest can be calculated based on the outer sequence (if it exists). But the problem with this method is that plenty of time is wasted on invalid set of chosen inner elements, where it can only be quitted when it hits the end of the loop.

Still getting TLE #13 to #21 (with Pypy, #15 to #21). Could I be completely wrong from the very beginning to start with multichoosing outer elements? I already have a guard to skip choices of outer sequence which does not satisfy sum(outer) == 2 * N * (2 * N + 1) - S * N, but still no hope.

EDIT 2: Finally cleared everything without switching to another language. As it turns out, if we start over and get rid of the mindset from the original problem, it's not that difficult.

The key insight here is to think about the triplets and combinations at the same time (somehow a hybrid method). I first generate an array of valid triplets (whose index is the sum of the 3 elements) similar to how we generate a list of factors of composite numbers.

We are concerned only about triplets[S]. Based on the multichoose combinations of the outer sequence and the sum(outer) == 2 * N * (2 * N + 1) - S * N condition, we get outer and inner without knowing their positions yet, except outer[0].

To make it more clear, I also created out_triplets whose elements are list of [inn1, inn2] and inn_triplets whose elements are list of [out, inn2]. Then we use a deque() which starts by appending elements from out_triplets[outer[0]] (both out, inn1, inn2 and out, inn2, inn1).

After that, we can use the last inn2 from popleft() as the index of inn_triplets to find all the valid (there's some conditions to it, such as no repeating out, no repeating inn2 except if it is the last element etc) next out, inn1, inn2 to add to the queue. When the sequence we get from popleft() is of desirable length, add it to the answers pool and don't add it to the queue. Repeat untill the queue is empty. Then do that again with another multichoose combination with brand new out_triplets and inn_triplets...

This implementation may look complicated, but once you get it straight, it is sort of clean and beautiful. The slowest test I got was 1.82s #21, and it is Python 2! That's of comparable speed to another C++ solution I found on the web.

And if you got WA #18, #20 and #21, make sure you sort the answers after joining them as string, not before joining.

EDIT 3: It's a solid 0.64s with Pypy. Fantastic.