You have a pile of items, each with a positive value, and some values repeat. Write exact_total_groups(values: list[int], target: int) -> list[list[int]] that returns every distinct group of items whose values add up to exactly target.
- Each item can be picked at most once. A value can appear in a group as many times as it appears in
values, but no more. - Groups are compared by their values, not by which items you picked: two groups holding the same values the same number of times are one group, and it must be returned once.
- The groups can come back in any order, and the values inside each group in any order. Return
[]if no group works.
exact_total_groups([4, 1, 3, 1, 2], 5) # [[4, 1], [3, 2], [3, 1, 1]] in some order
# (4 + 1 counts once, even though there are two 1s)
exact_total_groups([2, 2, 2], 4) # [[2, 2]]
exact_total_groups([5, 6], 4) # []
Constraints: 1 <= len(values) <= 100, 1 <= values[i] <= 50, 1 <= target <= 30.
Trying every subset of the items (up to 2^100) and throwing away repeats afterwards is hopeless. Aim for work proportional to the number of distinct partial groups whose sum stays within target: never build the same group twice.
Show hint
sort the values. When choosing which value goes into the next slot of the group, two equal values would lead to exactly the same groups, so only try the first of each run of equal values in that slot.