Customer Support: firstname.lastname@example.org
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:
- If you are a student, email to email@example.com to get special student discount.
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.
nums = [1, 2, 3]
target = 4
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(2, 1, 1)
Note that different sequences are counted as different combinations.
Therefore the output is 7.
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:
This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.
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
The above content is written by:
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn