Balanced Artifact Trays

Whether an array can form k groups of equal size and equal sum

MediumBacktrackingSymmetry PruningMemoization

A museum is preparing fragile artifacts for transport. Each artifact must be placed on exactly one of k trays.

The packing is acceptable only if:

  • Every tray contains the same number of artifacts.
  • Every tray has the same total artifact weight.

Given the positive integer artifact weights in weights and the number of trays k, return true if an acceptable packing exists, or false otherwise.

Artifacts with equal weights are still separate artifacts. The order of artifacts on a tray does not matter, and the trays have no individual restrictions.

Examples

Example 1

Input: weights = [1,2,3,4,5,6], k = 3
Output: true

The artifacts can be placed in pairs with weights (1, 6), (2, 5), and (3, 4). Each tray then contains two artifacts and has total weight 7.

Example 2

Input: weights = [1,1,1,3,3,3], k = 2
Output: false

Each tray would need three artifacts with total weight 6. Any three artifacts chosen from these weights have an odd total, so the required packing is impossible.

Example 3

Input: weights = [2,2,2,2,2], k = 2
Output: false

Five artifacts cannot be divided between two trays with the same number of artifacts.

Constraints

  • 1 <= weights.length <= 16
  • 1 <= weights[i] <= 50
  • 1 <= k <= weights.length

The intended solution uses backtracking with capacity checks, symmetry pruning, and memoization of failed states. Its worst-case running time is exponential. No sorting or mutation of the caller's input is required.

Hints

Show hint 1

The required artifact count and total weight for each tray are fixed. Check whether both can be integers before searching.

Show hint 2

Try heavier artifacts first. During one placement step, trays with the same current weight and artifact count are equivalent choices.

Follow-up questions

What an interviewer might ask once you have a working solution.

  • How would you return one valid packing instead of only deciding whether one exists?
  • How would the search change if each tray had its own required artifact count and weight?

Practice this with an AI interviewer

Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.

Start this problem