Subset Sum Equal To K
You are given an array/list ‘ARR’ of ‘N’ positive integers and an integer ‘K’. Your task is to check if there exists a subset in ‘ARR’ with a sum equal to ‘K’.

Note: Return true if there exists a subset with sum equal to ‘K’. Otherwise, return false.

For Example :

If ‘ARR’ is {1,2,3,4} and ‘K’ = 4, then there exists 2 subsets with sum = 4. These are {1,3} and {4}. Hence, return true.

Input Format :

The first line contains a single integer T representing the number of test cases. The first line of each test case contains two space-separated integers ‘N’ and ‘K’ representing the size of the input ‘ARR’ and the required sum as discussed above. The next line of each test case contains ‘N’ single space-separated integers that represent the elements of the ‘ARR’.

Output Format :

For each test case, return true or false as discussed above. Output for each test case will be printed in a separate line.

Note:

You don’t need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Subset Sum Equal To K

You are given an array/list ‘ARR’ of ‘N’ positive integers and an integer ‘K’. Your task is to check if there exists a subset in ‘ARR’ with a sum equal to ‘K’.

Note: Return true if there exists a subset with sum equal to ‘K’. Otherwise, return false.

For Example :

If ‘ARR’ is {1,2,3,4} and ‘K’ = 4, then there exists 2 subsets with sum = 4. These are {1,3} and {4}. Hence, return true.

Input Format :

The first line contains a single integer T representing the number of test cases.

The first line of each test case contains two space-separated integers ‘N’ and ‘K’ representing the size of the input ‘ARR’ and the required sum as discussed above.

The next line of each test case contains ‘N’ single space-separated integers that represent the elements of the ‘ARR’.

Output Format :

For each test case, return true or false as discussed above.
Output for each test case will be printed in a separate line.

Note:

You don’t need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 10^3
0 <= ARR[i] <= 10^9
0 <= K <= 10^9

Time Limit: 1 sec

Accepted Answer

The brute force approach is to use recursion. Generate all subsets and count the number of subsets with sum as 0. The time complexity of this approach would be exponential (2^n).
Dynamic programming can be used to optimize the above solution.
For every index i, we have two options, to include it in the sum or leave it. Suppose the sum of the elements we've chosen up to index 'i-1' is 'S'. From index ‘i’, we need to compute the number of subsets of the sub-array [i, N-1] whose sum equals -S.
dp[i][S] is defined as follows : the number of the subset of the subarray[i, N-1] with sum equal to '-S'.
Therefore, following recurrence relation can be used : dp[i][s] = dp[i+1][s+arr[i]] + dp[i+1][s]

Accepted Answer

Recursion

The idea is to generate all possible subsets and check if any of them sums up to ‘K’. This can be done through recursion.

Here is the algorithm:

subsetSumToK(N , K , ARR):

Initialize integer variable ‘ANS’ = ‘helper(ARR, N, K)’. Here ‘helper’ is the recursive function that returns true/false.
If ‘ANS’ is equal to 1 then:
- Return true.
Else:
- Return false.

helper(ARR, N, K):

Base case: If ‘N’ is less than or equal to 0:
- If ‘K’ is equal to 0:
  - Return 1.
- Else:
  - Return 0.
Initialize integer variable ‘X’ = ‘helper(ARR, N-1, K)’. Here, ‘ARR[N-1]’ is not included in the sum.
Initialize integer variable ‘Y’ = ‘helper(ARR, N-1, K - ARR[N-1])’. Here, ‘ARR[N-1]’ is included in the sum.
Return ‘X’ OR ‘Y’.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the size of ‘ARR’.

O(N) space is used in recursion for stack space at a time. Hence the space complexity is O(N).

Time Complexity: O(2^n)Explanation:

O(2^N), where ‘N’ is the size of ‘ARR’.

Since from each recursive call, we make 2 new recursive calls. Hence the time complexity is O(2^N).

Accepted Answer

Memoization

The idea is to generate all possible subsets and check if any of them sums up to ‘K’. Along with that, we will use memoization to store previously calculated results to avoid repetition and hence improving the time complexity.

Here is the algorithm:

subsetSumToK(N , K , ARR):

Create 2D array/list ‘MEMO’ of size (‘N’+1) * (‘K’ + 1) i.e. ‘MEMO[N+1][K+1]’.
Store -1 at all indices of ‘MEMO’. (This ‘MEMO’ array/list will be used to store the previously calculated results).
Initialize integer variable ‘ANS’ = ‘helper(ARR, N, K, MEMO)’. Here ‘helper’ is the recursive function that returns true/false.
If ‘ANS’ is equal to 1 then:
- Return true.
Else:
- Return false.

helper(ARR, N, K, MEMO):

Base case: If ‘N’ is less than or equal to 0:
- If ‘K’ is equal to 0:
  - Return 1.
- Else:
  - Return 0.
If ‘MEMO[N][K]’ is not equal to -1, i.e. value for this combination of ‘N’ and ‘K’ is already calculated, then:
- Return ‘MEMO[N][K]’.
Initialize integer variable ‘X’ = ‘helper(ARR, N-1, K, MEMO)’. Here, ‘ARR[N-1]’ is not included in the sum.
Initialize integer variable ‘Y’ = ‘helper(ARR, N-1, K - ARR[N-1], MEMO)’. Here, ‘ARR[N-1]’ is included in the sum.
‘MEMO[N][K]’ = ‘X’ OR ‘Y’.
Return ‘MEMO[N][K]’.

Space Complexity: OtherExplanation:

O(N*K), where ‘N’ is the size of ‘ARR’ and ‘K’ is the required sum.

O(N) space is used in recursion for stack space at a time and we are using a ‘MEMO’ array/list of size N*K for storing previously calculated results. Hence the space complexity is O(N*K).

Time Complexity: OtherExplanation:

O(N*K), where ‘N’ is the size of ‘ARR’ and ‘K’ is the required sum.

Due to memorization, repetitive recursive calls are eliminated. Hence, the function call for each combination of ‘N’ and ‘K’ is done only once. Hence, the time complexity is O(N*K).

Python (3.5)

'''    
    Time Complexity : O(N * K)
    Space Complexity : O(N * K)

    Where N is the number of elements in the array and
    K is the target sum. 
'''    

def helper(arr, n, k, memo):
    
    # Base condition.
    if n <= 0:
        
        # If k = 0, we reached target sum
        if k == 0:
            return 1
        
        else:
            return 0
        
        
    # If memo[n][k] not equal to -1
    # then result of n,k already calculated
    
    if (memo[n][k] != -1):
        return memo[n][k]
    
    # arr[n - 1] not taken in considertion
    x = helper(arr, n - 1, k, memo)
    y = 0
    
    if(k - arr[n - 1] >= 0):
        
        # arr[n - 1] taken in considertion
        y = helper(arr, n - 1, k - arr[n - 1], memo)
        
    # Store current result in memo
    if(x == 1 or y == 1):
        memo[n][k] = 1
        
    else:
        memo[n][k] = 0
        
    return memo[n][k]


def subsetSumToK(n, k, arr):
    
    # Declaring memo array and storing -1 in it
    memo = [[-1 for i in range(k + 1)] for j in range(n + 1)]
    
    
    # Calling recursive function.
    ans = helper(arr, n, k, memo)
    
    if ans == 1:
        return True
    
    else:
        return False

Java (SE 1.8)

/*

    Time Complexity : O(N * K)
    Space Complexity : O(N * K)

    Where N is the number of elements in the array and
    K is the target sum. 
    

*/


import java.util.Arrays;

public class Solution {
    
    public static int helper(int arr[], int n, int k, int[][] memo) {
        
         // Base condition.
        if (n <= 0) {
            // If k = 0, we reached target sum.
            if (k == 0) {
                return 1;
            } else {
                return 0;
            }
        }
    
        // If memo[n][k] not equal to -1
        // then result of n,k already calculated.
        if (memo[n][k] != -1) {
            return memo[n][k];
        }
    
    
        // arr[n-1] not taken in considertion.   
        int x = helper(arr, n - 1, k, memo);
        int y = 0;
        if(k - arr[n-1] >= 0){
            // arr[n-1] taken in considertion.
            y = helper(arr, n - 1, k - arr[n-1], memo);    
        }
    
        // Store current result in memo.
        if(x == 1 || y == 1){
            memo[n][k] = 1;
        }else{
            memo[n][k] = 0;
        }
        
        // Return current result.
        return memo[n][k];
    }

    public static boolean subsetSumToK(int n, int k, int arr[]){
       
        // Declaring memo array and storing -1 in it:
        int memo[][] = new int[n+1][k+1];
        
        for(int i = 0;i < memo.length; i++){
            Arrays.fill(memo[i], -1);
        }
        
        // Calling recursive function.
        int ans = helper(arr, n, k, memo);
    
        if (ans == 1) {
            return true;
        } else {
            return false;
        }
        
    }
}

C++ (g++ 5.4)

/*

    Time Complexity : O(N * K)
    Space Complexity : O(N * K)

    Where N is the number of elements in the array and
    K is the target sum. 
    

*/

int helper(vector < int > & arr, int n, int k, vector < vector < int >> & memo) {
    // Base condition.
    if (n <= 0) {
        // If k = 0, we reached target sum.
        if (k == 0) {
            return 1;
        } else {
            return 0;
        }
    }

    // If memo[n][k] not equal to -1
    // then result of n,k already calculated.
    if (memo[n][k] != -1) {
        return memo[n][k];
    }


    // arr[n-1] not taken in considertion.   
    int x = helper(arr, n - 1, k, memo);
    int y = 0;
    if(k - arr[n-1] >= 0){
        // arr[n-1] taken in considertion.
        y = helper(arr, n - 1, k - arr[n-1], memo);    
    }

    // Store current result in memo.
    memo[n][k] = x || y;
    // Return current result.
    return memo[n][k];
}

bool subsetSumToK(int n, int k, vector < int > & arr) {
    // Declaring memo array and storing -1 in it:
    vector < vector < int >> memo(n+1, vector < int > (k+1, -1));
    // Calling recursive function.
    int ans = helper(arr, n, k, memo);

    if (ans == 1) {
        return true;
    } else {
        return false;
    }
}

Accepted Answer

Dynamic Programming

The idea is to use dynamic programming to generate all the possible subsets and check if these subsets sum up to ‘K’.

Here is the algorithm:

Create a boolean 2D array/list ‘DP’ of size (‘N+1’)*(‘K+1’) i.e. ‘DP[N+1][K+1]’.
If ‘K’ is equal to 0, then the answer should be ‘true’. Hence, run a loop from 0 to ‘N’ (say iterator = ‘i’):
- ‘DP[i][0]’ = true.
If ‘K’ is not zero but ‘ARR’ is empty then the answer should be ‘false’. Hence, run a loop from 1 to ‘K’ (say iterator = ‘i’):
- ‘DP[0][i]’ = false.
To fill the ‘DP’ table, run a loop from 1 to ‘N’ (say iterator = ‘i’):
- Run a loop from 1 to ‘K’ (say iterator = ‘j’):
  - ‘DP[i][j]’ = ‘DP[i-1][j]’.
  - If ‘j’ is greater than equal to ‘ARR[i-1]’:
    - ‘DP[i][j]’ = ‘DP[i][j]’ OR ‘DP[i-1][j - ARR[i-1]]’.
Finally, return ‘DP[N][K]’.

Space Complexity: OtherExplanation:

O(N*K), where ‘N’ is the size of ‘ARR’ and ‘K’ is the required sum.

2D array/list of size N*K is created. Hence the space complexity is O(N*K).

Time Complexity: OtherExplanation:

O(N*K), where ‘N’ is the size of ‘ARR’ and ‘K’ is the required sum.

We are using two nested loops which run from 1 to ‘N’ and 1 to ‘K’ respectively. Hence, the time complexity is O(N*K).

Python (3.5)

'''

    Time Complexity : O(N * K)
    Space Complexity : O(N * K)

    Where N is the number of elements in the array and
    K is the target sum. 
    

'''  
    


def subsetSumToK(n, k, arr):
    
    # Declaring dp array
    dp = [[False for i in range(k + 1)] for i in range(n + 1)]
    
    for i in range(n + 1):
        dp[i][0] = True
    
    # If size of array = 0, answer always false
    for j in range(1, k + 1):
        dp[0][j] = False
        
    # Filling dp array
    for i in range(1, n + 1):
        
        for j in range(1, k + 1):
            
            dp[i][j] = dp[i - 1][j]
            
            if(arr[i - 1] <= j):
                
                dp[i][j] = dp[i][j] or dp[i - 1][j - arr[i - 1]]
                
    return dp[n][k]

Java (SE 1.8)

/*

    Time Complexity : O(N * K)
    Space Complexity : O(N * K)

    Where N is the number of elements in the array and
    K is the target sum. 
    

*/


public class Solution {

    public static boolean subsetSumToK(int n, int k, int arr[]){
       
        // Declaring dp array.
        boolean dp[][] = new boolean[n + 1][k + 1];
    
        // If required sum = 0, answer always true.
        for (int i = 0; i <= n; i++) {
            dp[i][0] = true;
        }
    
        // If size of array = 0, answer always false.
        for (int i = 1; i <= k; i++) {
            dp[0][i] = false;
        }
    
        // Filling dp array.
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                dp[i][j] = dp[i - 1][j];
                if (arr[i - 1] <= j) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j - arr[i - 1]];
                }
            }
        }
    
        return dp[n][k];
    }
}

C++ (g++ 5.4)

/*

    Time Complexity : O(N * K)
    Space Complexity : O(N * K)

    Where N is the number of elements in the array and
    K is the target sum. 
    

*/

bool subsetSumToK(int n, int k, vector < int > & arr) {
    // Declaring dp array.
    vector < vector < bool >> dp(n + 1, vector < bool > (k + 1));

    // If required price = 0, answer always true.
    for (int i = 0; i <= n; i++) {
        dp[i][0] = true;
    }

    // If size of array = 0, answer always false.
    for (int i = 1; i <= k; i++) {
        dp[0][i] = false;
    }

    // Filling dp array.
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            dp[i][j] = dp[i - 1][j];
            if (arr[i - 1] <= j) {
                dp[i][j] = dp[i][j] || dp[i - 1][j - arr[i - 1]];
            }
        }
    }

    return dp[n][k];
}

You are given an array/list ‘ARR’ of ‘N’ positive integers and an integer ‘K’. Your task is to check if there exists a subset in ‘ARR’ with a sum equal to ‘K’.

Note: Return true if there exists a subset with sum equal to ‘K’. Otherwise, return false.

For Example :

Input Format :

Output Format :

Note:

Constraints:

Top PayPal Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in PayPal Software Developer