<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]:
        # dp
        # score = dp[startIndex: n][prevPerm][unusedNums - 2^n]: from startIndex, perm is not filled, the lowest score
        # min: for num in unusedNums: score = dp[startIndx+1][num][unusedNums - num] + |lastElem - nums[num]|
        # if startIdx == n-1: += |lastElem - nums[num]| 
        # base case: dp[n][prevPerm][] = |last - nums[0]|
        
        # always start from 0
        n = len(nums)
        dpRecord = [[[None for _ in range(1<<(n+1))] for _ in range(n)] for _ in range(n)] # (score, permutation)
        
        def dp(startIndx=1, prevPerm=0, unusedNums=(1<<n)-1-1):
            # print(startIndx,prevPerm, bin(unusedNums), "| start")
            if startIndx == n: return (abs(prevPerm-nums[0]), [])
                                         
            if dpRecord[startIndx][prevPerm][unusedNums] != None: return dpRecord[startIndx][prevPerm][unusedNums]
        
            unusedNumsStr = str(bin(unusedNums))[2:]
            minScore = n*(n+1)//2
            minPerm = []
            for i in range(len(unusedNumsStr)):
                # print("i:", i, "n-1-i:", n-1-i)
                # if i >= len(unusedNumsStr): continue
                c = unusedNumsStr[len(unusedNumsStr)-1-i]
                if c == '0': continue
                # append i
                
                newUnusedNums = unusedNums - (1<<i)
                # print(startIndx,prevPerm, bin(unusedNums), "| appending i:",i, "newUnusedNums:", bin(newUnusedNums))
                
                dpScore, dpPerm = dp(startIndx+1, i, newUnusedNums)
                dpScore += abs(prevPerm - nums[i])
                # print(startIndx,prevPerm, bin(unusedNums), "| dpScore:", dpScore, "dpPerm:", [i]+ dpPerm)
                
                if dpScore < minScore:
                    minScore = dpScore
                    minPerm = [i]+dpPerm
                    
            dpRecord[startIndx][prevPerm][unusedNums] = (minScore, minPerm)
            # print(startIndx,prevPerm, bin(unusedNums),"| returning: ", minScore, minPerm)
            return (minScore, minPerm)
        
        
        _, minPerm = dp()
        return [0] +minPerm
            
        
6122