Maximum AND Sum of Array LeetCode solution in Java

1
class Solution {
2
  int[] memo;
3
  int[] nums;
4
  int numSlots;
5

6
  public int maximumANDSum(int[] nums, int numSlots) {
7
    this.memo = new int[1 << (2 * numSlots)];
8
    this.nums = nums;
9
    this.numSlots = numSlots;
10
    return helper(0, 0);
11
  }
12

13
  int helper(int numIndex, int set) {
14
    // Base case when we used all the numbers
15
    if (numIndex == nums.length) return 0;
16
    // Set informs BOTH the slots used and the numIndex. If the later
17
    // statement surprises you, think it like this: We must place all
18
    // the numbers in a slot, so how many slots are used in numIndex=10?
19
    // yes! 9 slots (because we will use the 10th now!), so the set will
20
    // have 10 ones. No other numIndex will have 9 ones. So having memo
21
    // with 2 dimentions would be redundant, as you would naver have a
22
    // combination of numIndex 3 with sets 1, 2, 4, 6.. etc, only
23
    // numIndex 2 will have those sets.
24
    if (memo[set] > 0) return memo[set] - 1; // I use memo-1 so I dont have to fill it with -1
25
    int max = 0;
26
    for (int i = 0; i < numSlots; i++) {
27
      int firstHalfSlot = (set & (1 << i)) == 0 ? i : -1; // -1 if it is used
28
      int secondHalfSlot =
29
          (set & (1 << (i + numSlots))) == 0 ? i + numSlots : -1; // -1 if it is used
30
      int slotChosen = firstHalfSlot > -1 ? firstHalfSlot : secondHalfSlot;
31
      if (slotChosen < 0) continue; // both slots are used
32
      int andSum = 0;
33
      if (slotChosen >= numSlots) andSum = ((slotChosen - numSlots) + 1) & nums[numIndex];
34
      else andSum = (slotChosen + 1) & nums[numIndex];
35
      // By adjusting the set in the recursion signature
36
      // I am backtracking in an elegant way.
37
      max = Math.max(max, andSum + helper(numIndex + 1, set | 1 << slotChosen));
38
    }
39
    memo[set] = max + 1; // I use memo+1 so I dont have to fill it with -1
40
    return max;
41
  }
42
}