<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>

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        # solution redone here, original solution further below
        n = len(nums) // 2

        dp = {}
        def f(mask):
            level = 1 + (mask.bit_count() // 2)
            if level > n:
                return 0
            if mask in dp:
                return dp[mask]

            res = 0
            for i in range(2 * n):
                for j in range(i + 1, 2 * n):
                    if mask & (1 << i) == 1 << i or mask & (1 << j) == 1 << j:
                        continue
                
                    new_mask = mask | (1 << i)
                    new_mask = new_mask | (1 << j)
                    val = self.gcd(nums[i], nums[j])
                    res = max(res, level * val + f(new_mask))
            
            dp[mask] = res
            return res
        
        return f(0)
        
    def gcd(self, x, y):
        y, x = max(x, y), min(x, y)
        while y % x > 0:
            y, x = x, y % x
        return x

































    #     memo = [-1] * (2 ** len(nums))
    #     self.recurse(nums, 0, len(nums) // 2, memo)
    #     return memo[0]

    # def recurse(self, nums, mask, level, memo):
    #     if level == 0:
    #         return 0
    #     if memo[mask] != -1:
    #         return memo[mask]
        
    #     m = len(nums)
    #     res = 0
    #     for i in range(m):
    #         for j in range(i + 1, m):
    #             # check that nums[i] and nums[j] have not been used before
    #             # note that it is possible for new_mask != mask even though
    #             # nums[i] and nums[j] have been used before
    #             if mask & (1 << i) == 0 and mask & (1 << j) == 0:
    #                 new_mask = mask | (1 << i) | (1 << j)
    #                 score = level * self.gcd(nums[i], nums[j])
    #                 res = max(
    #                     res,
    #                     score + self.recurse(nums, new_mask, level - 1, memo)
    #                 )
    #     memo[mask] = res
    #     return res

    # def gcd(self, a, b):
    #     if a == 1 or b == 1:
    #         return 1
    #     if max(a, b) % min(a, b) == 0:
    #         return min(a, b)
    #     return self.gcd(min(a, b), max(a, b) % min(a, b))





    # """Solution 2:"""
    # # def maxScore(self, nums: List[int]) -> int:
    # #     return self.recurse(nums, [False] * len(nums), len(nums) // 2)
    
    # # def recurse(self, nums, used, level):
    # #     n = len(nums)
    # #     if level == 0:
    # #         return 0
    # #     res = 0
    # #     for i in range(n):
    # #         for j in range(i + 1, n):
    # #             if used[i] == False and used[j] == False:
    # #                 num1, num2 = nums[i], nums[j]
    # #                 used[i], used[j] = True, True
    # #                 score = level * self.gcd(num1, num2)
    # #                 res = max(
    # #                     res,
    # #                     score + self.recurse(nums, used, level - 1)
    # #                 )
    # #                 used[i], used[j] = False, False
    # #     return res

    # # def gcd(self, a, b):
    # #     if a == 1 or b == 1:
    # #         return 1
    # #     if max(a, b) % min(a, b) == 0:
    # #         return min(a, b)
    # #     return self.gcd(min(a, b), max(a, b) % min(a, b))
2403