<p>You are given an array <code>nums</code> which is a <span data-keyword="permutation">permutation</span> of <code>[0, 1, 2, ..., n - 1]</code>. The <strong>score</strong> of any permutation of <code>[0, 1, 2, ..., n - 1]</code> named <code>perm</code> is defined as:</p>

<p><code>score(perm) = |perm[0] - nums[perm[1]]| + |perm[1] - nums[perm[2]]| + ... + |perm[n - 1] - nums[perm[0]]|</code></p>

<p>Return the permutation <code>perm</code> which has the <strong>minimum</strong> possible score. If <em>multiple</em> permutations exist with this score, return the one that is <span data-keyword="lexicographically-smaller-array">lexicographically smallest</span> among them.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,0,2]</span></p>

<p><strong>Output:</strong> <span class="example-io">[0,1,2]</span></p>

<p><strong>Explanation:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2024/04/04/example0gif.gif" style="width: 235px; height: 235px;" /></strong></p>

<p>The lexicographically smallest permutation with minimum cost is <code>[0,1,2]</code>. The cost of this permutation is <code>|0 - 0| + |1 - 2| + |2 - 1| = 2</code>.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [0,2,1]</span></p>

<p><strong>Output:</strong> <span class="example-io">[0,2,1]</span></p>

<p><strong>Explanation:</strong></p>

<p><strong><img alt="" src="https://assets.leetcode.com/uploads/2024/04/04/example1gif.gif" style="width: 235px; height: 235px;" /></strong></p>

<p>The lexicographically smallest permutation with minimum cost is <code>[0,2,1]</code>. The cost of this permutation is <code>|0 - 1| + |2 - 2| + |1 - 0| = 2</code>.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= n == nums.length &lt;= 14</code></li>
	<li><code>nums</code> is a permutation of <code>[0, 1, 2, ..., n - 1]</code>.</li>
</ul>

class Solution:
    def findPermutation(self, nums: List[int]) -> List[int]:

        n = len(nums) 
        memo = [[] for _ in range(n)] 
        for i in range(n):
            for j in range(n):
                if i == j: continue
                memo[i].append((abs(i - nums[j]), j)) 
            # memo[i].sort() 

        bestPaths = {source: {} for source in range(n)}
        bestPaths[0][0] = (0, None) 
        masks = [2 ** i for i in range(n)] 
        def search(source: int, score: int, free: int) -> int: # tuple: 
            # print(f"path [nodes free]: {f'{source}':<7} [{free:>0{n}b}]; score: {score}")
            if free in bestPaths[source]:
                return score + bestPaths[source][free][0] 

            bestContinuation = 0xFF # upper bound: 16**2-1 = 2**8-1 
            bestNextEl = None 
            for scoreDiff, nextEl in memo[source]:
                if free & masks[nextEl]: 
                    if not nextEl and free != 1: continue # nextEl = 0 has to be last 
                    nc = search(nextEl, score + scoreDiff, free ^ masks[nextEl]) 
                    if nc < bestContinuation or (nc == bestContinuation and nextEl < bestNextEl):
                        bestContinuation = nc 
                        bestNextEl = nextEl 
            bestPaths[source][free] = (bestContinuation - score, bestNextEl) 
            return bestContinuation 

        free = 2 ** n - 1 
        search(0, 0, free) 

        response = [0] 
        while (ne := bestPaths[response[-1]][free][1]) != 0: 
            response.append(ne) 
            free ^= masks[ne] 
        return response        
1835