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

In the ith operation (1-indexed), you will:


	Choose two elements, x and y.
	Receive a score of i * gcd(x, y).
	Remove x and y from nums.


Return the maximum score you can receive after performing n operations.

The function gcd(x, y) is the greatest common divisor of x and y.

&nbsp;
Example 1:

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


Example 2:

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


Example 3:

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


&nbsp;
Constraints:


	1 &lt;= n &lt;= 7
	nums.length == 2 * n
	1 &lt;= nums[i] &lt;= 106


from functools import lru_cache

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        def gcd(a, b):
            while a:
                a, b = b%a, a
            return b
        halfplus = len(nums)//2 + 1
        @lru_cache(None)
        def dfs(mask, k):
            if k == halfplus:
                return 0
            res = 0
            for i in range(len(nums)):
                for j in range(i+1, len(nums)):
                    if not(mask & (1<<i)) and not(mask &(1<<j)):
                        res = max(res, k*gcd(nums[i], nums[j])+dfs(mask|(1<<i)|(1<<j), k+1))
            return res
        return dfs(0, 1)
class Solution {
    public int maxScore(int[] nums) {
        int n = nums.length;
        Map<Integer, Integer> gcdVal = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                gcdVal.put((1 << i) + (1 << j), gcd(nums[i], nums[j]));
            }
        }
        
        int[] dp = new int[1 << n];
        
        for (int i = 0; i < (1 << n); ++i) {
            int bits = Integer.bitCount(i); // how many numbers are used
            if (bits % 2 != 0) // odd numbers, skip it
                continue;
            for (int k : gcdVal.keySet()) {
                if ((k & i) != 0) // overlapping used numbers
                    continue;
                dp[i ^ k] = Math.max(dp[i ^ k], dp[i] + gcdVal.get(k) * (bits / 2 + 1));
            }
        }
        
        return dp[(1 << n) - 1];
    }
    
    public int gcd(int a, int b) {
        if (b == 0)   
            return a;     
        return gcd(b, a % b);   
    }
}

// Time: O(2^n * n^2)
// Space: O(2 ^ n)
int dp[16384];
int gcd_table[14][14];

class Solution {
public:
    int maxScore(vector<int>& nums) {
        memset(dp, -1, sizeof(dp));
        int sz = nums.size();

        // Build the GCD table 
        for (int i = 0; i < sz; ++i) {
            for (int j = i+1; j < sz; ++j) {gcd_table[i][j] = gcd(nums[i], nums[j]);}
        }

        // Looping from state 0 to (1<<sz)-1
        dp[0] = 0;
        for (int s = 0; s < (1<<sz); ++s) {
            int cnt = __builtin_popcount(s);
            if (cnt &1 )continue; // bitcount can't be odd
            for (int i = 0; i < sz; ++i) {
                if (s & (1<<i)) continue;
                for (int j = i+1; j < sz; ++j) {
                    if (s & (1<<j)) continue;
                    int next_state = s^(1<<i)^(1<<j);
                    dp[next_state] = max(dp[next_state], dp[s] + (cnt/2+1)*gcd_table[i][j]);
                }
            }
        }
        return dp[(1<<sz)-1];
    }
};
var maxScore = function(nums) {
    
    function gcd(a, b) {
        if(!b) return a;
        return gcd(b, a % b);
    }
    
    const memo = new Map();
    
    function recurse(arr, num1, op) {
        if(!arr.length) return 0;
        
        const key = arr.join() + num1;
        if(memo.has(key)) return memo.get(key);
        
        let max = 0;
        
        for(let i = 0; i < arr.length; i++) {
            const nextArr = [...arr.slice(0, i), ...arr.slice(i+1)];
            
            if(num1) {
                const currGCD = gcd(num1, arr[i]);
                const rest = recurse(nextArr, null, op+1);
                max = Math.max(max, ((op * currGCD) + rest));
            } else {
                const rest = recurse(nextArr, arr[i], op);
                max = Math.max(max, rest);
            }
        }
        memo.set(key, max);
        return max;
    }
    return recurse(nums, null, 1);
};
Maximize Score After N Operations