it hangs in the balance

approach

every group has to weigh total / k, so the search is for the smallest subset that hits that target. the numbers are sorted and ksum generates every combination of exactly k numbers with that sum: it recurses on k and ends in a two-pointer two_sum.

the size starts at two and grows until some combination exists; among those, the one with the smallest product wins. the code doesn't check that the remaining packages can be split into the other groups, which was enough here. part 1 uses three groups and part 2 four.

the trick

grow the group size from the bottom, so the first size with any solution is already the minimum.

def ksum(arr, k, start, target):
    if k == 2:
        yield from two_sum(arr, start, target)
        return
    for i in range(start, len(arr) - k + 1):
        yield from ((*tup, arr[i]) for tup in ksum(arr, k - 1, i + 1, target - arr[i]))