Gift Bundle Combinations

Problem: Gift Bundle Combinations

In the spirit of the upcoming holiday celebrations, imagine you are preparing gift bundles for a community event. You have a list of gift items each with a price, and you want to create bundles that exactly sum up to a given budget. Each gift item can be chosen multiple times.

Task:

Write a function countGiftBundles that takes an array of positive integers giftPrices and an integer budget. The function should return the number of unique combinations of gifts that add up exactly to the budget. Note that the order of gifts in the combination does not matter.

Example:

• Input: giftPrices = [2, 3, 5], budget = 8
• Output: 3

Explanation: The valid combinations are:

• 2 + 2 + 2 + 2
• 2 + 3 + 3
• 3 + 5

Hint: This problem is similar to the coin change problem and can be approached using dynamic programming. Consider creating an array dp where dp[i] represents the number of combinations to form the budget i, with dp[0] initialized to 1.