Count Subsets with Sum K

Moderate
0/80
profile
Contributed by
470 upvotes
Asked in company
PharmEasy

Problem statement

You are given an array 'arr' of size 'n' containing positive integers and a target sum 'k'.


Find the number of ways of selecting the elements from the array such that the sum of chosen elements is equal to the target 'k'.


Since the number of ways can be very large, print it modulo 10 ^ 9 + 7.


Example: 
Input: 'arr' = [1, 1, 4, 5]

Output: 3

Explanation: The possible ways are:
[1, 4]
[1, 4]
[5]
Hence the output will be 3. Please note that both 1 present in 'arr' are treated differently.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains two space-separated integers ‘n’ and 'k', denoting the size of the array and the target sum.

The second line contains ‘n’ space-separated integers denoting the elements of the array.


Output Format : 
Print the number of ways we can choose elements from 'arr' such that their sum is equal to 'k'.


Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Sample Input 1 :
4 5
1 4 4 5


Sample Output 1 :
 3


Explanation For Sample Output 1:
The possible ways are:
[1, 4]
[1, 4]
[5]
Hence the output will be 3. Please note that both 1 present in 'arr' are treated differently.


Sample Input 2 :
3 2
1 1 1


Sample Output 2 :
3


Explanation For Sample Output 1:
There are three 1 present in the array. Answer is the number of ways to choose any two of them.


Sample Input 3 :
3 40
2 34 5


Sample Output 3 :
0


Expected time complexity :
The expected time complexity is O('n' * 'k').


Constraints:
1 <= 'n' <= 100
0 <= 'arr[i]' <= 1000
1 <= 'k' <= 1000

Time limit: 1 sec
Hint

Check for every possible way such that the sum is ‘k’.

Approaches (3)
Brute Force (Recursion)

The basic idea is to go over recursively to find the way such that the sum of chosen elements is ‘k’. 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 ‘k’ by the value of the element at the end. At any point, if we have ‘k’ = 0 then we can say that we have found the set of integers such that the sum of the set is equal to ‘k’.

Let us define a function findWaysHelper(i, k, n, arr), where ‘i’ is the current index of the array we are at, ‘k’ is the remaining sum that we have to make, ‘n’ is the size of the array, ‘arr’ is the array which is given to us. This function gives us the number of ways ‘k’ can be made if we can take elements from ‘i’ to n - 1.

Here is the algorithm:

  • findWaysHelper function:
    • If ‘k’ is less than 0:
      • Return 0
    • If ‘i’ is equal to ‘n’:
      • If ‘k’ is equal to 0:
        • Return 1
      • Return 0
    • Declare an integer variable ‘ans’ and initialize it with 0.
    • ‘ans’ = findWaysHelper(‘i’ + 1, ‘k’ - ‘arr[i]’, ‘n’, ‘arr’).
    • Update ‘ans’ as ‘ans’ = ‘ans’ + findWaysHelper(‘i’ + 1, ‘k’, ‘n’, ‘arr’).
    • Return ‘ans’ % (10^9 + 7).
  • Given function findWays:
    • Declare an integer variable ‘n’ and initialize it as the size of the array.
    • Return findWaysHelper(0, ‘k’, ‘n’, ‘arr’).
Time Complexity

O(2 ^ n), where ‘n’ is the size of the array.

Each element of the array has 2 choices whether to include in a subset or not. So there is a 2 ^ n number of subsets. Hence, the overall time complexity will be O(2 ^ n).

Space Complexity

O(k), where ‘k’ is the sum which we want.

The recursive stack for the ‘findWaysHelper’ function can contain at most ‘k’. Therefore, the overall space complexity will be O(k).

Code Solution
(100% EXP penalty)
Count Subsets with Sum K
Full screen
Console