Gift Basket DP

In the holiday spirit, imagine you're creating unique gift baskets from a store of available gift items. Each gift has a positive integer price and you have a total budget. Your task is to determine the number of distinct ways you can choose gifts (using an unlimited supply of each gift) such that their total price exactly matches your budget. The order in which the gifts are chosen does not matter.

Problem Statement

Given an array of positive integers prices and an integer total, implement a function giftBasketCount(prices, total) that returns the number of distinct combinations of gifts that add up to total.

Example

For prices = [2, 3, 5] and total = 7, the output should be 2.

Explanation:

• One combination is: 2 + 2 + 3
• Another combination is: 2 + 5

If no combination of gifts can sum up to total, return 0.

Hints

• Consider using dynamic programming to solve this problem efficiently.
• You might use a bottom-up approach by initializing a DP array where the index represents a possible sum and the value at that index represents the number of ways to achieve that sum.
• Remember, since each gift can be chosen an unlimited number of times, you may revisit options as you build up your solution.

Happy coding and enjoy the holiday season!