🙏

জয়  শ্রী  রাম

🕉

---

Problem Statement:

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target. You can use each number as many times as you want.

Example:
nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.
Therefore the output is 7.

Solution:

This problem is similar to Coin Change: Total no. of Combinations Possible.

This problem, consisting of a target W and a nums[] array, can be thought of as follows:

Given a knapsack which can carry a maximum of W weight we need to fill it up to exactly W weight using one or more instances of items with weight nums[i]. For every item we have the option to either include it or not include it.

This is nothing but extension of Unbounded Knapsack Concept. We will use the template discussed in Unbounded Knapsack Problem chapter to solve this problem as shown below:

Java Code:

Login to Access Content

Python Code:

Login to Access Content

Tip:

Often times if a problem mentions that you can include an element as many time as you want, there is a chance that the problem could be solved using Unbounded Knapsack Concept.

Instructor: