Gift Package Combinations

Dynamic Programming Holiday Dp Easy Medium

Problem Description

During the holiday season, it's time to prepare special gift packages. Given an array of positive integers representing the weights of available gifts and a target package weight, determine the number of unique combinations of gifts that sum exactly to the target weight. Note: The order of the gifts does not matter (i.e., combinations differing only in the order of items are considered the same).

For example, given weights [2, 3, 5] and a target weight of 8, one valid set of combinations might be:

  • 3 + 5
  • 2 + 2 + 2 + 2 (if multiple instances of a weight are allowed)

Assumption: You can use each gift weight an unlimited number of times.

Your task is to implement a function countGiftCombinations(weights, target) that returns the total number of unique combinations to reach exactly the target weight using dynamic programming.

Constraints

  • weights is a list/array of positive integers.
  • target is a positive integer.
  • The function should be optimized for cases where target might be relatively large.

Example

Input:

weights = [2, 3, 5]
target = 8

Output:

3

Explanation: There are 3 ways to reach the target weight (if order is not considered):

  1. 2+2+2+2
  2. 2+3+3
  3. 3+5

Good luck and happy coding!