1171. Combinations When Each Value Has a Stock Limit

Given n distinct positive values, a stock count for each, and a target t, print every combination totalling t that uses no value more times than its stock allows.

3 6 1 2 3 3 2 1 -> 1 1 1 3 1 1 2 2 1 2 3

Stock 3 of the value 1, stock 2 of the value 2, stock 1 of the value 3. So 1 1 1 3 is allowed and 2 2 2 is not, because only two 2s exist.

## What most people try first

Solve it as problem 1168 does, with unlimited reuse, and throw away the combinations that use too many of something. That is correct and it explores branches that were already impossible: with stock 1 of the value 1 and a target of 20, the unlimited search walks twenty levels deep down a path that died at level two.

The other common attempt is to expand the stock into a plain list, writing three 1s and two 2s out as five separate values, and then solve it as problem 1169. That is also correct and it is a real technique, worth knowing: it converts a bounded problem into an at-most-once problem. It costs the expansion, which can be large when the stock counts are large, and it needs that problem's duplicate-skip rule to avoid producing each combination many times.

## The method

Keep the counts and decrement them as the search uses them:

go(i, rem): if rem == 0: record cur; return for j in i .. n-1: if a[j] > rem: break if left[j] == 0: continue left[j] -= 1 cur.push(a[j]); go(j, rem - a[j]); cur.pop() left[j] += 1

Note the recursion goes to j, not j + 1, because another copy of the same value may still be in stock. The index never goes backwards, which is what keeps each combination non-decreasing and therefore produced once. And left[j] is state, so it must be restored on the way out exactly like cur.

## Why it is correct

The search builds exactly the non-decreasing sequences in which each value appears at most its stock count times: the index is non-decreasing by construction, and left[j] is the stock of a[j] minus the number of copies currently in cur, because it is decremented at the push and restored at the undo. A sequence is recorded when the remaining target reaches 0. Every valid combination is reached, since at each step its next value is at index i or later and has stock remaining. The break cuts nothing legal because the values are sorted and positive.

## 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.

A value whose stock is 0 can never be used, and t is at least 1, so the empty combination is never an answer.

## Cost

Proportional to the number of combinations times O(t) to print, with the two prunes removing the branches that cannot finish. The recursion is at most t deep.

Constraints - `1 ≤ n ≤ 8` - `1 ≤ t ≤ 30` - `1 ≤ a[i] ≤ 100` - `0 ≤ stock of a[i] ≤ 10` - All values are distinct. - It is guaranteed that at most 300 combinations total `t`.