What is the smallest $N$ such that the set of the first $N$ cubes can be partitioned into $K$ subsets whose sums are equal?

(See the original framing in terms of golden orbs at fivethirtyeight)

Solution

My approach is not only computational, but pretty brute-force to boot: for each number $K$ of subsets, we step through the sets of the first $N$ cubes, and search the tree of partial assignments of cubes to partitions until we find a complete assignment to $K$ same-sum subsets.

On my PC, this code finds the solution for $K$ up to $8$ in about $72$ minutes: $1, 12, 23, 24, 24, 35, 41, 47$.

I’ll be curious to see if there are analytic approaches to this. I’m sure there are at least more efficient computational ones, given that puzzle author Dean Ballard has determined values up to at least $N = 10$.

import time

# Returns True if arr can be  
# partitioned into K subsets with equal sum
# Modified from a method found online:
# https://www.geeksforgeeks.org/partition-set-k-subsets-equal-sum/

def isEqualSumPartitionPossible(arr, K): 

  if (K == 1): 
      return True
    
  # If total number of partitions is more than N, or
  # array sum is not divisible by K, then a partition 
  # into equal-sum subsets is not possible  
  N = len(arr)
  if (N < K): 
      return False
  sum = 0
  for i in range(N): 
      sum += arr[i]  
  if (sum % K != 0): 
      return False

  targetSum = sum // K

  # initialize first subset sum as   
  # last element of array and mark that as taken 
  subsetSums = [0] * K  
  taken = [0] * N  
  subsetSums[0] = arr[N - 1]  
  taken[N - 1] = True

  # We avoid explicit recursion to hopefully save a
  # little runtime, using a state stack instead.
  # [Actual result: no time savings.]
  stack = [[subsetSums,taken,0,N-1]]
  while not stack == [] :
    subsetSums,taken,curIdx,limitIdx = stack.pop()
    if subsetSums[curIdx] == targetSum: 
            
      # current index (K - 2) means we've found
      # (K - 1) subsets of sum targetSum. Untaken 
      # numbers must then form the Kth.
      if (curIdx == K - 2): 
        return True
      
      # otherwise start next partition
      stack.append([list(subsetSums),list(taken),curIdx+1,N-1])
      continue

    # still adding to a partition. we start from limitIdx and add  
    # untaken elements into current partition
    for i in range(limitIdx, -1, -1): 
            
      if (taken[i]): 
        continue
      
      taken[i] = True
      subsetSums[curIdx] += arr[i]

      # if no greater than targetSum, add task to stack
      if (subsetSums[curIdx] <= targetSum):
        stack.append([list(subsetSums),list(taken),curIdx,i-1])
                               
      # unmark the element and remove from sum as we move 
      # to previous element in arr  
      taken[i] = False
      subsetSums[curIdx] -= arr[i]
  return False
      
# Main loop
startTime = time.time()
K = 0
while True:
  K += 1
  arr = []
  N = 0
  while True:
    N += 1
    arr.append(N**3)
    if (isEqualSumPartitionPossible(arr, K)): 
      print(K,N, "in", (time.time()-startTime))
      break