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, or at least more efficient computational ones.

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