It is Diwali sale time. The array candidates holds the prices of items you like, and target is your budget. Pick some items so that their prices add up to exactly target. Return all the different price combinations.
Each item can be bought only once. Two items can have the same price, and they are two separate items. But two combinations with the same prices count as one. Do not repeat a combination. Return the answer in any order.
Examples
Example 1:
Input: candidates = [4,2,2,6,3], target = 8
Output: [[2,2,4],[2,6]]
Explanation: Two combinations add up to 8: 2 + 2 + 4 and 2 + 6.
Example 2:
Input: candidates = [5,3,3,1], target = 7
Output: [[1,3,3]]
Explanation: Only 1 + 3 + 3 makes 7.
Example 3:
Input: candidates = [9,10], target = 5
Output: []
Explanation: Every item costs more than the budget, so the list is empty.