https://leetcode.com/problems/maximize-score-after-n-operations

When you see constraints of this problem you should think about dynaimc programming on subsets. Let us define by dp(bitmask) the answer for subproblem, where we can use only numbers with 1 bits, for example if nums = [1,2,3,4,5,6] and bitmask = 010111, we can use numbers 2, 4, 5, 6.

How we can calculate dp(bitmask)? We need to look at all pairs of not used yet numbers and take dp of the resulting mask. Then choose maximum among all possible candidates.

Complexity: time complexity is O(2^(2n)*n^2), because we have 2^(2n) different bitmasks and for each masks and for each of them we have O(n^2) transitions to other bitmasks. Also I precalculated all gcds, which will give you complexity O(n^2*log M), where M is the biggest number in nums. Space complexity is O(2^(2n)).

class Solution:
    def maxScore(self, nums):
        n = len(nums)
        gcds = {(j, k): gcd(nums[j], nums[k]) for j, k in combinations(range(n), 2)}

        @lru_cache(None)
        def dfs(bitmask):
            if bitmask == 0: return 0
            
            cand = 0
            n_z_bits = [j for j in range(n) if bitmask&(1<<j)]
            for j, k in combinations(n_z_bits, 2):
                q = bitmask^(1<<j)^(1<<k)
                cand = max(cand, dfs(q) + (n+2 - len(n_z_bits))//2*gcds[j, k])
            return cand

        return dfs((1<<n) - 1)

If you like the solution, you can upvote it on leetcode discussion section: Problem 1799