Exact-Change Combinations From a Cash Drawer
A kirana shop's cash drawer holds individual currency notes (in rupees), some of duplicate denominations. Find every distinct set of notes that sums exactly to a customer's bill amount — each physical note may be used at most once.
Problem
Given an array notes of rupee values (which may contain duplicates) and a target bill amount, return all unique combinations of notes that sum to target. Each note may be used at most once in a combination, and the result must not contain duplicate combinations.
Input
An integer array notes of length [1, 100] and an integer target. Values in [1, 50].
Output
A list of unique integer lists, each summing to target.
Constraints
- 1 <= notes.length <= 100
- 1 <= notes[i] <= 50
- 1 <= target <= 30
Examples
Example 1
Input
notes = [10,1,2,7,6,1,5], target = 8
Output
[[1,1,6],[1,2,5],[1,7],[2,6]]
Each distinct note-set summing to 8, no repeats.
Example 2
Input
notes = [2,5,2,1,2], target = 5
Output
[[1,2,2],[5]]
Duplicate 2-rupee notes do not produce duplicate combinations.