<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)
        dp = [[(float('inf'), None, []) for _ in range(n)] for _ in range(1 << n)]
        dp[1][0] = (0, -1, [0])


        for mask in range(1 << n):
            for end in range(n):
                if mask & (1 << end):
                    prev_mask = mask & ~(1 << end)
                    if prev_mask == 0:
                        continue
                    for prev in range(n):
                        if prev_mask & (1 << prev):
                            new_cost = dp[prev_mask][prev][0] + abs(prev - nums[end])
                            new_path = dp[prev_mask][prev][2] + [end]
                            current_entry = dp[mask][end]

                            if (new_cost < current_entry[0]) or (new_cost == current_entry[0] and new_path < current_entry[2]):
                                dp[mask][end] = (new_cost, prev, new_path)


        final_mask = (1 << n) - 1
        min_cost = float('inf')
        best_path = []
        for i in range(n):
            final_cost, _, path = dp[final_mask][i]
            final_cost += abs(i - nums[0])
            if final_cost < min_cost or (final_cost == min_cost and path < best_path):
                min_cost = final_cost
                best_path = path

        return best_path
6578