<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]:
        # the minimum score is represented by 2 * (num_cycles - 1)
        # and can be obtained by reversing the cycles and then
        # rotating them so the difference between consecutive
        # cycles is 0
        n = len(nums)

        # ex:
        #        0 1 2 3 4 5 6 7
        # nums = 3 2 5 4 6 1 0 7
        # here, perm[0] should be 0 and perm[1] = 6 to ensure 0 total cost for the first cycle
        # then, perm[2] = 4
        def cycles(perm: List[int]) -> int:
            vis = [False for _ in perm]
            n = len(perm)
            cnt = 0
            
            for start in range(n):
                if not vis[start]:
                    vis[start] = True
                    cnt += 1
                    current = start
                    while not vis[perm[current]]:
                        vis[perm[current]] = True
                        current = perm[current]
            return cnt


        # easier with dp. starting from this idea
        minScore = 2 * (cycles(nums) - 1)
        fin = (1 << len(nums)) - 1

        fixedElems = {}

        # return True if you can reach the end with the minimum cost
        def dp(cost: int, state: int, prev: int) -> bool:
            if state == fin:
                return cost + abs(nums[0] - prev) == minScore
            
            for i in range(n):
                if state & (1 << i):
                    continue
                if cost + abs(nums[i] - prev) > minScore:
                    continue
                if dp(cost + abs(nums[i] - prev), state | (1 << i), i):
                    fixedElems[state, prev] = i
                    return True
            return False
            
        # redo the path
        dp(0, 1, 0)
        res = [0]

        current = 0
        mask = 1
        for i in range(n - 1):
            current = fixedElems[(mask, current)]
            res.append(current)

            mask = mask | (1 << current)
        return res

        

68