Combination Sum — Valid Bill Denominations

Problem

Given an array of coin denominations (e.g., [1, 2, 5, 10, 20, 50, 100, 200, 500]) and a target amount, find all unique combinations that sum to the target. Each denomination can be used multiple times.

Example

denominations = [1, 2, 5], target = 5
Output: [[1,1,1,1,1],[1,1,1,2],[1,2,2],[5]]

Constraints

• 1 ≤ denominations.length ≤ 30
• 2 ≤ target ≤ 40
• No duplicate denominations

Follow-up

If you only need the count of combinations (not enumerate them), how does your approach change? Can you do it in O(target × n)?