Leetcode 1799

The dp part of the problem is not hard, but mask is difficult, and that is what we have to take a closer look to. I need to review this question tmr again.

class Solution {
    int[] memo;
    public int maxScore(int[] nums) {
        memo = new int[ 1 << nums.length];
        Arrays.fill(memo,-1);
        return dp(nums, 0, 0);
    }
    private int dp(int[] nums, int mask, int pairsPicked){
        // base case 
        if(2 * pairsPicked == nums.length) return 0; // we picked all number
        // solved case
        if(memo[mask] != -1) return memo[mask];

        int max = 0;
        for(int i = 0; i < nums.length; i ++){
            for(int j = i + 1; j < nums.length; j ++){
                // If the numbers are same, or already picked, then we move to next number.
                if (((mask >> i) & 1) == 1 || ((mask >> j) & 1) == 1) {
                    continue;
                }

                // Both numbers are marked as picked in this new mask.
                int newMask = mask | (1 << i) | (1 << j);
                 // Calculate score of current pair of numbers, and the remaining array.
                int currScore = (pairsPicked + 1) * gcd(nums[i], nums[j]);
                int remainingScore = dp(nums, newMask, pairsPicked + 1);

                // Store the maximum score.
                max = Math.max(max, currScore + remainingScore);
                // We will use old mask in loop's next interation, 
                // means we discarded the picked number and backtracked.
            }
        }
        return memo[mask] = max;
    }
    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}