Subset sum equal to target

In this article, we will solve the most asked coding interview problem: Subset sum equal to target.

In this article, we will be going to understand the pattern of dynamic programming on subsequences of an array. We will be using the problem “Subset Sum Equal to K”.

First, we need to understand what a subsequence/subset is.

A subset/subsequence is a contiguous or non-contiguous part of an array, where elements appear in the same order as the original array.
For example, for the array: [2,3,1] , the subsequences will be [{2},{3},{1},{2,3},{2,1},{3,1},{2,3,1}} but {3,2} is not a subsequence because its elements are not in the same order as the original array.

Problem Link: Subset Sum Equal to K

We are given an array ‘ARR’ with N positive integers. We need to find if there is a subset in “ARR” with a sum equal to K. If there is, return true else return false.

Examples

Example:

Approach - Tabulation 1D

• Though process seems similar to two sum for every number we check from the given number to target if it is possible to reach sum target and at the end we say at k if it is possible
• Ye second loop mein kuch aisa socho ki agar minus x karke koi mil gaya matlab wo element toh present hai arr mein isme jo number arr men hai hi nahi usme true toh kabhi nahi aayega toh wo automatically handled hai aur koi check mahi karna hi arr mein hai ki nahi
• Ab target se start karke x tak isiliye kyuki number toh inke beech mein hi hoga
• O(n*k), O(n)

public class Solution {
    public static boolean subsetSumToK(int n, int k, int arr[]){
        // Write your code here.
        boolean[] dp = new boolean[k+1];
        dp[0] = true;
 
        for (int x: arr) {
            for (int t = k; t >= x; t--) {
                if (dp[t-x])
                    dp[t] = true;
            }
        }
 
        return dp[k];
    }
}

public class Solution {
    public static boolean subsetSumToK(int n, int k, int arr[]){
        // Write your code here.
        boolean[] prev = new boolean[k+1];
        prev[0] = true;
        if (arr[0] <= k)
            prev[arr[0]] = true;
 
        for (int i = 1; i < n; i++) {
            boolean curr[] = new boolean[k+1];
            for (int target = 1; target <= k; target++) {
                boolean notPick = prev[target];
                boolean pick = false;
 
                if (arr[i] <= target)
                    pick = prev[target - arr[i]];
 
                curr[target] = notPick || pick;    
            }
            prev = curr;
        }    
 
        return prev[k];
    }
}