Combination Sum Count

Algorithms and Data Structures: TheAlgorist.com

System Design: SystemsDesign.Cloud

Low Level Design: LowLevelDesign.io

Frontend Engineering: FrontendEngineering.io
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.
Instructor:
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn