Last Updated: 15 Jan, 2022
Combination Sum IV
Moderate
Asked in companies
You are given an array of distinct integers and you have to tell how many different ways of selecting the elements from the array are there such that the sum of chosen elements is equal to the target number tar.
Note: Two ways are considered the same if for every index the contents of both the ways are equal example way1=[1,2,3,1] and way2= [1,2,3,1] both way1 and way 2 are the same.
But if way1 =[1,2,3,4] and way2= [4,3,2,1] then both ways are different.
Input is given such that the answer will fit in a 32-bit integer.
For Example:
If N = 3 and tar = 5 and array elements are [1,2,5] then the number of possible ways of making sum = 5 are:
(1,1,1,1,1)
(1,1,1,2)
(1,2,1,1)
(2,1,1,1)
(1,1,2,1)
(2,2,1)
(1,2,2)
(2,1,2)
(5)
Hence the output will be 9.
Input Format :
The first line of the input contains an integer, 'T’, denoting the number of test cases.
The first line of each test case will contain two space-separated integers ‘N’ and “tar”, denoting the size of the array and the given integer.
The second line of each test case contains ‘N’ space-separated integers denoting elements of the array.
Output Format :
For each test case, print the number of ways that satisfy the condition mentioned in the problem statement.
Print a separate line for each test case.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= N <= 200
1 <= nums[i] <= 1000
All the elements will be unique
1 <= tar <= 1000
Time limit: 1 sec
Approaches
The basic idea is to go over recursively to find the way such that the sum of chosen elements is “tar”. For every element, we have two choices
1. Include the element in our set of chosen elements.
2. Don’t include the element in our set of chosen elements.
When we include an element in the set then we decrease the x by the value of the element at the end. At any point, if we have x=0 then we can say that we have found the set of integers such that the sum of the set is equal to x.
Let us define a function “numberOfWays( sum, n, num)”, where “sum” is the remaining sum that we have to make, ‘n’ is the size of the array, num is the array which is given to us. Each time we have ‘n’ elements from which we have to take one.
Here is the algorithm:
- numberOfWays function:
- If sum is less than 0
- return 0
- If sum is 0
- Return 1
- Declare an integer variable “ans” and initialize it with 0.
- Iterate over n(say ‘j’)
- Update ans as ans + numberOfWays(sum-num[j], n, num)
- Return ans
- If sum is less than 0
- given function:
- Declare an integer variable n and initialize it as the size of the array.
- Return numberOfWays( tar, n, num).
The basic idea is to store the results of the recursive calls to avoid repetition. We can memorize the results of our function calls in an array (say, ‘DP’).
So,let's first define dp[i]
Dp[i] is the number of ways that we can make sum equal to ‘i’.
Let us define a function “numberOfWays( sum, n, num,dp)”, where “sum” is the remaining sum that we have to make, ‘n’ is the size of the array, num is the array which is given to us and “dp” array is used to memorize the results.
Here is the algorithm :
- numberOfWays function:
- If sum is less than 0
- return 0
- If sum is 0
- Return 1
- If dp[sum] != -1
- Return dp[sum]
- Declare an integer variable “ans” and initialize it with 0.
- Iterate over n(say ‘j’)
- Update ans as ans + numberOfWays(sum-num[j], n, num,dp)
- Update dp[sum] as ans.
- Return ans.
- If sum is less than 0
- given function:
- Declare an integer variable ‘n’ and initialize it as the size of the array.
- Declare an array “dp” of size “tar” + 1 and initialize it with -1.
- Return numberOfWays( tar, n, num,dp).
The idea is similar to the previous approach. In this approach, we use an iterative way to store the count of a number of ways in which a sum can be made.
dp[i]= the number of ways to make sum ‘i’.
If we already have calculated the number of ways to make sum [0,1,..,i-1] then we can iterate over all the elements of the array and try to put an ith element of the array as the last element to make sum equal to ‘i’.
Here is the algorithm :
- Declare an integer variable ‘n’ and initialize it as the size of the array.
- Declare an array “dp” of size “tar” + 1 and initialize it with 0.
- Set dp[0] = 1
- Run a loop from ‘i’ =1 to ‘i’ = tar
- Run another loop for iterating over all the elements of the array, say iterator ‘j’
- If i-num[j]>=0
- Update dp[i] as dp[i]+=dp[i-num[j]]
- Run another loop for iterating over all the elements of the array, say iterator ‘j’
- Return dp[tar]