Solving the leftover dice combinations problem

diceCombinations.py

from functools import cache

"""
You are throwing a dice for a fixed number of times (`throwCount`), of which
you know the average of the total score. The total score is calculated by
adding up all the dice scores from each throw. You only know the score of a
few of the dice throws.

Find all possible combinations of the remaining dice that fulfill
the above information.

throwCount: Total of number of dice throws
diceAverage: Average score of all thrown dices
someThrown: Scores of some of the dice that had been thrown (<= throwCount)
"""

# Assuming order of dice thrown doesn't matter
def diceCombinations(throwCount: int, diceAverage: int, someThrown: list[int]):
  remaining = throwCount - len(someThrown)
  remainingSum = diceAverage * throwCount - sum(someThrown)
  possible = []
  seen = set()

  # Find all combinations of dice that can make up remaining sum
  @cache
  def dp(total: int, tries: int, combi: tuple[int]):
    if tries == 0 and total == 0:
      combiTuple = tuple(sorted(combi))
      if combiTuple in seen or len(list(combi)) == 0:
        return
      possible.append(list(combi))
      seen.add(combiTuple)
      return
    elif tries <= 0 or total <= 0:
      return

    for i in range(1, 7):
      dp(total - i, tries - 1, combi + (i,))

  dp(remainingSum, remaining, ())
  return possible

# Any combi that adds up to 8 and is within 3 throws: 1 combi -> [1, 4, 3]
print(diceCombinations(7, 3, [4, 6, 1, 2]))
# `someThrown` already lists all 7 scores: result -> []
print(diceCombinations(7, 3, [4, 6, 1, 2, 1, 1, 6]))