1169. Combinations From a Bag With Repeats
Given n positive values which may REPEAT, and a target t, print every
distinct combination totalling t, where each listed value may be used at most
once. Two combinations are the same if they use the same values the same number
of times.
5 8
1 1 2 5 5 -> 1 2 5
There are four different ways to pick a 1, a 2 and a 5 out of that bag,
and they are all the same combination, so the line appears once.
## What most people try first
Run the search from problem 1148, which assumes distinct values, and
deduplicate the finished lines with a set. It is correct and it is the wrong
place to fix the problem: the 2^n subsets of the positions are built and most
are discarded. With six copies of 1 and a target of 3 there are 20 subsets
that work and one answer.
## Two different repeat problems, and only one of them is here
It is worth separating this from problem 1168. There, the input values are distinct and a value may be used many times, so the search recurses into the SAME index. Here, the input has repeated values and each listed copy is used at most once, so the search recurses into the NEXT index and the repeats have to be suppressed. Mixing the two up gives a search that finds combinations using more copies of a value than the bag contains.
## The method
Sort, so equal values are adjacent, then combine the prune from 1148 with the duplicate-branch skip from 1153:
go(i, rem):
if rem == 0: record cur; return
for j in i .. n-1:
if a[j] > rem: break # sorted: nothing later fits
if j > i and a[j] == a[j-1]: continue # same value, same call
cur.push(a[j]); go(j + 1, rem - a[j]); cur.pop()
Both lines are needed and they do different jobs. The break cuts branches that
cannot reach the target. The continue cuts branches that would reach it by a
route another branch already takes.
## Why it is correct
Each distinct combination is reached exactly once. Reached: write it in sorted
order and build it by always taking the earliest unused position holding the
next value needed; at every step that position is the first occurrence of its
value in the suffix the call is looking at, so the skip never refuses it.
Exactly once: two paths that first differ chose different j in the same call,
where the skip leaves at most one position per distinct value, so the values and
therefore the combinations differ.
## The output convention, shared by every problem in this block
Each combination is printed on its own line with single spaces between its
values. Two combinations are compared position by position NUMERICALLY, and
when one is a prefix of the other the shorter comes first. If no combination
reaches the target, print none.
Since t is at least 1 and every value is positive, a printed combination
always has at least one value.
## Cost
Proportional to the number of distinct combinations times O(n) to print, plus
the pruned tests. At n = 16 with all values 1 and t = 8 that is one answer
and a search that never descends past depth 8.
Constraints - `1 ≤ n ≤ 16` - `1 ≤ t ≤ 60` - `1 ≤ a[i] ≤ 50` - Values may repeat.
Input
The first line contains two integers n and t.
The second line contains n space-separated positive integers, which may repeat.
Output
Print every distinct combination totalling t on its own line, its values in non-decreasing order separated by single spaces, the lines ordered as described. Print none if no combination totals t.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.