<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)
        full_mask = (1 << n) - 1
        
        @cache
        def minimum_cost_and_permutation(mask, last_value):
            # for each (bitmask of unused values, last value)
            # return the minimum cost and its respective minimum permutation

            if mask == full_mask:  # all values are used
                next_value = 0
                return abs(last_value - nums[next_value]), [last_value]
            
            mincost = float('inf')
            minperm = []
            
            # for each possible next value (which is unused)
            for next_value in range(1, n):
                if (1 << next_value) & mask == 0:
                    
                    # call the recursive function with the updated bitmask and last value
                    cost, perm = minimum_cost_and_permutation(mask ^ (1 << next_value), next_value)

                    # add the cost of |perm[i] - nums[perm[i+1]]| = |last_value - nums[next_value]|
                    cost += abs(last_value - nums[next_value])
                    
                    if cost < mincost:
                        # no need to compare perm because next_value is iterated in increasing order
                        mincost = cost
                        minperm = perm
                            
            return mincost, [last_value] + minperm
        
        # the first element is always zero (by observation, probably provable)
        return minimum_cost_and_permutation(1, 0)[1]
43600