<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]:
        INF = 10**6
        N = len(nums)
        cost = [[INF for _ in range(N)] for _ in range(N)]
        for i in range(N):
            for j in range(N):
                if i == j:
                    continue
                cost[i][j] = abs(i - nums[j])

        smallest_next: dict[tuple[int, int], int] = {}
        
        powers = [pow(2,i) for i in range(N)]

        @functools.lru_cache(maxsize=1000000)
        def dfs(last_elem: int, curr_used: int) -> int:
            
            rem_verts = [i for i in range(N) if curr_used & powers[i] == 0]
            
            
            if len(rem_verts) == 1:
                smallest_next[last_elem, curr_used] = rem_verts[0]
                return cost[last_elem][rem_verts[0]] + cost[rem_verts[0]][0]
            
            ans = INF
            best_next = 0

            for x in rem_verts:
                new_score = cost[last_elem][x]
                new_ans = new_score + dfs(last_elem=x, curr_used=curr_used|powers[x])
                if new_ans < ans:
                    best_next = x
                    ans = new_ans
            
            smallest_next[last_elem, curr_used] = best_next

            return ans

        dfs(0, 1)
        my_perm = [0]
        curr_last, curr_test_used = 0, 1
        while len(my_perm) < N:
            curr_last = smallest_next[curr_last, curr_test_used]
            my_perm.append(curr_last)
            if len(my_perm) == N:
                break
            curr_test_used |= powers[curr_last]

        return my_perm
2893