• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.



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:



This is a Premium content.
Please subscribe to Algorithms course to access the code.




Python Code:



This is a Premium content.
Please subscribe to Algorithms course to access the code.





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.

The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave