<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)
        ans = n*n
        ansPerm = None
        BIGNUM = 10**9

        @functools.cache
        def dp(mask: int, prev: int) -> Tuple[int, Tuple[int]]:
            if mask == 0:
                return (abs(prev - nums[0]), ())
            ans = BIGNUM
            ansPerm = ()
            for j in range(1, n):
                if mask & (1 << j) != 0:
                    x, y = dp(mask & ~(1 << j), j)
                    if x + abs(prev - nums[j]) < ans:
                        ans = x + abs(prev - nums[j])
                        ansPerm = (j, *y)
            return (ans, ansPerm)
        
        return [0] + list(dp(int('1'*(n-1)+'0', 2), 0)[1])
                    

        def dp(i: int, currAmt: int, soFar: int, prev: int) -> int:
            nonlocal n, ans, ansPerm
            if i == n:
                newAmt = currAmt + abs(curr[-1] - nums[0])
                if newAmt < ans:
                    ans = newAmt
                    ansPerm
            if currAmt > ans: return BIGNUM
            soln = BIGNUM
            for j in range(1, n):
                if soFar & (1 << j) != 0:
                    soln = min(soln, dp(i+1, currAmt + abs(prev-nums[j]), soFar | (1 << j)))
            return soln
        


        heap = [(0, (0,))]
        while heap:
            amt, curr = heapq.heappop(heap)
            # print(f"{amt=}, {curr=}")
            if len(curr) == n:
                amt += abs(curr[-1] - nums[0])
                # print(f"consider {amt=}, {curr=}")
                if amt < ans:
                    # print(f"accepted")
                    ans = amt
                    ansPerm = curr
            elif amt >= ans:
                continue
            else:
                for x in range(1, n):
                    if x in curr: continue
                    heapq.heappush(heap, ( amt+abs(curr[-1]-nums[x]), tuple(list(curr)+[x]) ))
        return ansPerm

2250