<p>You are given <code>nums</code>, an array of positive integers of size <code>2 * n</code>. You must perform <code>n</code> operations on this array.</p>

<p>In the <code>i<sup>th</sup></code> operation <strong>(1-indexed)</strong>, you will:</p>

<ul>
	<li>Choose two elements, <code>x</code> and <code>y</code>.</li>
	<li>Receive a score of <code>i * gcd(x, y)</code>.</li>
	<li>Remove <code>x</code> and <code>y</code> from <code>nums</code>.</li>
</ul>

<p>Return <em>the maximum score you can receive after performing </em><code>n</code><em> operations.</em></p>

<p>The function <code>gcd(x, y)</code> is the greatest common divisor of <code>x</code> and <code>y</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2]
<strong>Output:</strong> 1
<strong>Explanation:</strong>&nbsp;The optimal choice of operations is:
(1 * gcd(1, 2)) = 1
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [3,4,6,8]
<strong>Output:</strong> 11
<strong>Explanation:</strong>&nbsp;The optimal choice of operations is:
(1 * gcd(3, 6)) + (2 * gcd(4, 8)) = 3 + 8 = 11
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4,5,6]
<strong>Output:</strong> 14
<strong>Explanation:</strong>&nbsp;The optimal choice of operations is:
(1 * gcd(1, 5)) + (2 * gcd(2, 4)) + (3 * gcd(3, 6)) = 1 + 4 + 9 = 14
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 7</code></li>
	<li><code>nums.length == 2 * n</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>6</sup></code></li>
</ul>

from math import gcd
from typing import List

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        n = len(nums) // 2
        
        # Memoization dictionary to store the results of subproblems
        memo = {}
        
        # Function to calculate the maximum score using backtracking and memoization
        def dp(mask, pairs_picked, nums):
            # If all elements have been used, return 0
            if pairs_picked == n:
                return 0
            
            # If this subproblem has already been solved, return the stored result
            if (mask, pairs_picked) in memo:
                return memo[(mask, pairs_picked)]
            
            max_score = 0
            
            # Try all possible pairs of unused elements
            for first_index in range(2 * n):
                for second_index in range(first_index + 1, 2 * n):
                    # If either of the elements is already used, skip
                    if (mask >> first_index) & 1 or (mask >> second_index) & 1:
                        continue
                    
                    # Create a new mask to mark the picked elements as used
                    new_mask = mask | (1 << first_index) | (1 << second_index)
                    
                    # Calculate the score for the current pair and recursively solve for the remaining elements
                    score = (pairs_picked + 1) * gcd(nums[first_index], nums[second_index])
                    score += dp(new_mask, pairs_picked + 1, nums)
                    
                    # Update the max_score with the maximum score found
                    max_score = max(max_score, score)
            
            # Store the result of this subproblem in the memoization dictionary
            memo[(mask, pairs_picked)] = max_score
            return max_score
        
        # Start with an empty mask and 0 pairs picked
        return dp(0, 0, nums)

# Example usage:
solution = Solution()
nums = [1, 2, 3, 4, 5, 6]
print(solution.maxScore(nums))  # Output: 14
1913