Problem statement

https://binarysearch.com/problems/Connect-Sticks/

Solution

Let us keep state (mask, last), where mask is bitmask for not used sticks yet and last is the end of the last stick. Then given mask and last we can try to find all candidates.

Complexity

Time complexity is O(2^n*m^2) for time and O(2^n*m) for space, where n = len(S) and m = 6 here.

Code

class Solution:
    def solve(self, S):
        n = len(S)

        @lru_cache(None)
        def dp(mask, last):
            ans = 0
            for i, (x, y) in enumerate(S):
                for b, e in (x, y), (y, x):
                    if e == last and mask >> i & 1:
                        ans = max(ans, dp(mask^(1<<i), b) + 1)
            return ans

        return max(dp((1<<n) - 1, x) for x in range(1, 7))