Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Problem

Submissions

Hints & solutions

Discuss

Count Subsets with Sum K

Moderate

0/80

Contributed by

430 upvotes

Asked in company

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 :

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 :

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 :

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 1

Hint 2

Hint 3

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

Approaches (3)

Approach 1

Approach 2

Approach 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).

(100% EXP penalty)

Count Subsets with Sum K

Saswat Kumar Sahoo

Interview problems

All test cases passed in java

import java.util.*;
import java.io.*;

public class Solution {
    public static int findWays(int num[], int tar) {
// Write your code here.
int n = num.length;
int m = (int)(1e9+7);
long[][] dp = new long[n][tar+1];
// for(int i=0;i<n;i++) dp[i][0] = 1;
// if(num[0] <= tar) dp[0][num[0]] = 1;
for(int i=0;i<n;i++) {
for(int j=0;j<=tar;j++) {
if(i == 0) {
if(j == 0 && num[i] == 0) dp[i][j] = 2;
else if(j == 0 || j == num[i]) dp[i][j] = 1;
else dp[i][j] = 0;
continue;
}
long take = 0;
long notTake = dp[i-1][j]%m;
if(num[i] <= j) take = dp[i-1][j-num[i]]%m;
dp[i][j] = (take%m + notTake%m)%m;
}
}
return (int)(dp[n-1][tar]%m);
}
}

29 views

0 replies

1 upvote

akhil ade

Interview problems

Can u guys help me what wrong with mycode?????

from typing import List

def findWays(arr: List[int], k: int) -> int:

dp_arr = [[None for i in range(k + 1)]for _ in range(len(arr))]

def dp(ind, target, dp_arr):

if target == 0:

return 1

if ind == 0:

if arr[0] == target:

return 1

else:

return 0

if dp_arr[ind][target] != None:

return dp_arr[ind][target]

not_take = dp(ind - 1, target, dp_arr)

take = 0

if arr[ind] <= target:

take = dp(ind - 1, target - arr[ind], dp_arr)

dp_arr[ind][target] = take + not_take

return dp_arr[ind][target]

return dp(len(arr) -1,k,dp_arr)

38 views

0 replies

0 upvotes

Akanksha Maurya

Interview problems

testcase related issue

3 4 0 1 3 what's wrong with this test case????

66 views

2 replies

1 upvote

Arpit Jatav

Interview problems

46 test case is wrong

when i submit my dp solution it is giving me wrong answer on test case 46 which is

3 4

0 1 3

the correct answer of this test case is 1 because there is only one possible subset {1,3} which will give the sum 4. But in the expected output it is showing 2 as the answer. can you please help

56 views

3 replies

1 upvote

Rupesh Kumar Sah

Interview problems

both memoization and tabulation solution comment sol==memoization and without comment sol==tabulation #striver sheet

int mod=(int)(1e9+7);

// int solve(vector<int>&arr,int n,int target,

// vector<vector<int>>&dp

// ){

// if(n==0)

// {

// if(target==0&& arr[0]==0) return 2;

// if(target==0||target==arr[0]) return 1;

// return 0;

// }

// if(dp[n][target]!=-1){

// return dp[n][target];

// }

// //not take

// int nottake=solve(arr,n-1,target,dp);

// int take=0;

// if(arr[n]<=target){

// take=solve(arr,n-1,target-arr[n],dp);

// }

// return dp[n][target]=(take+nottake)%mod;

// }

int findWays(vector<int>& arr, int k)

{

int n=arr.size();

vector<vector<int>>dp(n,vector<int>(k+1,0));

if(arr[0]==0)dp[0][0]=2;

else

dp[0][0]=1;

if(arr[0]<=k&&arr[0]!=0){

dp[0][arr[0]]=1;

}

for(int i=1;i<n;i++){

for(int target=0;target<=k;target++){

//not take

int nottake=dp[i-1][target];

int take=0;

if(arr[i]<=target){

take=dp[i-1][target-arr[i]];

}

dp[i][target]=(take+nottake)%mod;

}

return dp[n-1][k];

// return solve(arr,n-1,k,dp);

}

124 views

0 replies

0 upvotes

Ankit Raj

Interview problems

What wrong in this my code 46/50 testcases passed

mod=10**9+7

N=len(arr)

t = [[0 for i in range(k+1)] for j in range(N+1)]

for i in range(N+1):

t[i][0] = 1

for i in range(1,N+1):

for j in range(1,k+1):

if arr[i-1]<=j:

t[i][j] = (t[i-1][j-arr[i-1]] + t[i-1][j])%mod

else:

t[i][j] = t[i-1][j]%mod

return t[N][k]%mod

97 views

1 reply

1 upvote

Abhijit Kulkarni

Interview problems

Issue with input in submission

I think there might be an issue with the below input:

5 13
12 14 3 18 2 

When I run the same code through custom tests I get 0 which is expected but when I submit it, it fails at this input. So I am not sure what is wrong. Please check out my code and LMK if there is any issue with it.

from typing import List

def solve(index, target, arr, dp):
    if target == 0:
        return 1
    if index < 0:
        return 0
    if dp[index][target] == -1:
        pick = 0
        if target >= arr[index]:
            pick = solve(index-1, target - arr[index], arr, dp)
        not_pick = solve(index-1, target, arr, dp)
        dp[index][target] = pick + not_pick
    return dp[index][target]

def findWays(arr: List[int], k: int) -> int:
    n = len(arr)
    dp = [[-1] * (k+1) for i in range(n)]
    countZeros = arr.count(0)
    return (2**countZeros) * solve(n-1, k, arr, dp)

74 views

0 replies

7 upvotes

ganesha M

Interview problems

C++ optimal soln_ !!!

int MOD = 1000000007;

int findWays(vector<int>& arr, int k)

{

int n = arr.size();

vector<int>dp(k+1, 0);

dp[0] = 1;

for(int i=0;i<n;i++){

for(int j=k;j>=arr[i];j--){

dp[j] = (dp[j] + dp[j-arr[i]]) % MOD;

}

return dp[k];

}

229 views

1 reply

1 upvote

sahil shukla

Interview problems

can anyone tell what have i done wrong in this code

from typing import List

def findWays(arr: List[int], k: int) -> int:

def g(arr,target_sum):

m = 10 ** 9

n = len(arr)

dp = [[0] * (target_sum + 1) for _ in range(n)]

for i in range(n):

dp[i][0] = 1

for j in range(1, target_sum + 1):

if arr[0] == j:

dp[0][j] = 1

for i in range(1, n):

for j in range(1, target_sum + 1):

if arr[i] <= j:

dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - arr[i]]) % m

else:

dp[i][j] = (dp[i - 1][j])

if arr[0] == 0:

return dp[n - 1][target_sum] + 1

return dp[n - 1][target_sum]

return g(arr,k)

96 views

0 replies

0 upvotes

Pranav Angrish

Interview problems

Whats wrong with my tabulation

if i change j=1 to j=0 in the nested loop, it works fine, it should not happen as i am already handling the base case for total = 0 separately making that row 1

int findWays(vector<int>& arr, int k)

{

int n = arr.size();

vector<vector<int>>dp(n,vector<int>(k+1,0));

for(int i = 0 ; i < n ; i++){

dp[i][0] = 1;

}

for(int i = 0 ; i <= k ; i++){

if(arr[0] == i) dp[0][i] = 1;

}

if(arr[0] == 0) dp[0][0] = 2;

int mod = 1e9+7;

for(int i = 1 ; i < n ; i++){

for(int j = 1 ; j <= k ; j++){

int notTaken = dp[i-1][j];

int taken = 0;

if(arr[i] <= j) taken = dp[i-1][j-arr[i]];

dp[i][j] = (notTaken + taken)%mod;

}

return dp[n-1][k];

}

75 views

1 reply

0 upvotes

Console