Santa's Gift Finder

Problem Description

Santa is looking for the perfect combination of gifts for children while staying within budget. Given an array of gift prices and a budget (target amount), write a function that returns all unique combinations of gift prices that add up exactly to the target amount. Each gift price can be used multiple times in a combination.

Requirements

• Your solution should use a backtracking approach to explore possible gift combinations.
• Return a list of lists, where each inner list is a valid combination that sums to the target.
• The order of combinations and the order within each combination does not matter.

Example

For example, given gift prices [2, 3, 5] and a target of 8, one possible solution is:

[
  [2, 2, 2, 2],
  [2, 3, 3],
  [3, 5]
]

Note: There might be other valid combinations as well.

Hint

Use a recursive backtracking technique to explore all possible combinations, and make sure to check the running sum at each step.