progress

~/problems / Backtracking

Combination Sum II

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

medium ~30 min

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.

⭐ Bonus: a speed test with many repeated values earns a star if you never build the same group twice (work proportional to the distinct partial groups within target). Trying every subset (up to 2^100) and throwing away repeats is hopeless there.

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.

Topic: Recursion and backtracking. Choose, recurse, un-choose: subsets, permutations, N-queens, pruning.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc