Subset sum equals to target

The idea is to generate all pssible subsets and whenever a single subsets is found whose sum is equal to the given target, simply return true. As, all the subsets needs to generated, recursion can be used to solve this problem.

Steps to form the recursive solution:

Express the problem in terms of indexes: The array will have an index but there is one more parameter “target”. So, we can say that initially, we need to find(n-1, target) which means that we need to find whether there exists a subset in the array from index 0 to n-1, whose sum is equal to the target.

So, f(ind, target) will check whether a subset exists in the array from index 0 to index 'ind' such that the sum of elements is equal to the target.

Try out all possible choices at a given index: As all the subsets needs to be generated, we will use the pick/non-pick technique.There will be two choices in each function call:

Do not include the current element in the subset: First try to find a subset without considering the current index element. For this, make a recursive call to f(ind-1,target).

Include the current element in the subset: Now try to find a subset by considering the current index element as part of subset. As the current element(arr[ind]) is included, the remaining target sum will be target - arr[ind]. Therefore, make a function call of f(ind-1,target-arr[ind]).

Note: Consider the current element in the subset only when the current element is less or equal to the target.

/*It is pseudocode  and it is not tied to 
any specific programming  language*/

f(ind, target){
    not pick = f(ind-1, target)
    pick = false
    if(target <= arr[ind]{
        pick = f(ind-1, target - arr[ind])
    }
           
}

Return (pick || not pick): As we are looking for only one subset whose sum of elements is equal to target, if any of the one among 'pick' or 'not pick' returns true, it means the required subset is found so, return true.

/*It is pseudocode  and it is not tied to 
any specific programming  language*/

f(ind, target){
   not pick = f(ind-1, target)
    pick = false
    if(target <= arr[ind]{
        pick = f(ind-1, target - arr[ind])
    }
    return (pick || not pick)    
}

Base cases: There will be tow base cases, First, when target == 0, it means that the subset is already found from the previous steps, so simply return true. Another, when ind==0, it means we are at the first element, so return arr[ind]==target. If the element is equal to the target it will return true else false.

#include <bits/stdc++.h>
using namespace std;

class Solution{
private:
    /* Function to check if there is a subset of arr
    with a sum equal to 'target' using recusion*/
    bool func(int ind, int target, vector<int>& arr) {
        // Base cases
        if (target == 0)
            return true;

        if (ind == 0)
            return arr[0] == target;

        // Try not taking the current element into subset
        bool notTaken = func(ind - 1, target, arr);

        /* Try taking the current element into the 
        subset if it doesn't exceed the target*/
        bool taken = false;
        if (arr[ind] <= target)
            taken = func(ind - 1, target - arr[ind], arr);

        // Return the result
        return notTaken || taken;
    }
public:
    /* Function to check if there is a subset
    of 'arr' with a sum equal to 'target'*/
    bool isSubsetSum(vector<int>& arr, int target) {
        // Return the result
        return func(arr.size() - 1, target, arr);
    }
};
int main() {
    vector<int> arr = {1, 2, 3, 4};
    int target = 4;

    //Create an instance of Solution class
    Solution sol;
    
    // Call the subsetSumToK function and print the result
    if (sol.isSubsetSum(arr, target))
        cout << "Subset with the given target found";
    else
        cout << "Subset with the given target not found";

    return 0;
}
import java.util.*;

class Solution {
    /* Function to check if there is a subset of
    arr with sum equal to 'target' using recursion*/
    private boolean func(int ind, int target, int[] arr) {
        // Base cases
        if (target == 0)
            return true;
        
        if (ind == 0)
            return arr[0]== target;
        
        // Try not taking the current element into subset
        boolean notTaken = func(ind - 1, target, arr);
        
        /* Try taking the current element into the
        subset if it doesn't exceed the target*/
        boolean taken = false;
        if (arr[ind] <= target)
            taken = func(ind - 1, target - arr[ind], arr);
        
        // Return the result
        return notTaken || taken;
    }
    
    /* Function to check if there is a subset
    of 'arr' with sum equal to 'target'*/
    public boolean isSubsetSum(int[] arr, int target) {
        // Return the result
        return func(arr.length - 1, target, arr);
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4};
        int target = 4;
        
        // Create an instance of Solution class
        Solution sol = new Solution();
        
        // Call the isSubsetSum function and print the result
        if (sol.isSubsetSum(arr, target))
            System.out.println("Subset with the given target found");
        else
            System.out.println("Subset with the given target not found");
    }
}
class Solution:
    """ Function to check if there is a subset of arr
    with sum equal to 'target' using recursion"""
    def func(self, ind, target, arr):
        # Base cases
        if target == 0:
            return True
        
        if ind == 0:
            return arr[0] == target
        
        # Try not taking the current element into subset
        notTaken = self.func(ind - 1, target, arr)
        
        """ Try taking the current element into the
        subset if it doesn't exceed the target"""
        taken = False
        if arr[ind] <= target:
            taken = self.func(ind - 1, target - arr[ind], arr)
        
        # Return the result
        return notTaken or taken
    
    """ Function to check if there is a subset
    of 'arr' with sum equal to 'target'"""
    def isSubsetSum(self, arr, target):
        # Return the result
        return self.func(len(arr) - 1, target, arr)
    
if __name__ == "__main__":
    arr = [1, 2, 3, 4]
    target = 4
    
    # Create an instance of Solution class
    sol = Solution()
    
    # Call the isSubsetSum function and print the result
    if sol.isSubsetSum(arr, target):
        print("Subset with the given target found")
    else:
        print("Subset with the given target not found")
class Solution {
    /* Function to check if there is a subset of arr
    with sum equal to 'target' using recursion*/
    func(ind, target, arr) {
        // Base cases
        if (target === 0)
            return true;
        
        if (ind === 0)
            return arr[0] === target;
        
        // Try not taking the current element into subset
        let notTaken = this.func(ind - 1, target, arr);
        
        /* Try taking the current element into the
        subset if it doesn't exceed the target*/
        let taken = false;
        if (arr[ind] <= target)
            taken = this.func(ind - 1, target - arr[ind], arr);
        
        // Return the result
        return notTaken || taken;
    }
    
    /* Function to check if there is a subset
    of 'arr' with sum equal to 'target'*/
    isSubsetSum(arr, target) {
        // Return the result
        return this.func(arr.length - 1, target, arr);
    }
}

let arr = [1, 2, 3, 4];
let target = 4;

// Create an instance of Solution class
let sol = new Solution();

// Call the isSubsetSum function and print the result
if (sol.isSubsetSum(arr, target))
    console.log("Subset with the given target found");
else
    console.log("Subset with the given target not found");

Time Complexity: O(2^(N)), where N is the length of the array. As, for each index, ther are two possible options.

Space Complexity:O(N), at maximum the depth of the recursive stack can go upto N.

If we draw the recursion tree, we will see that there are overlapping subproblems. Hence the DP approaches can be applied to the recursive solution.

In order to convert a recursive solution to memoization the following steps will be taken:

Declare a dp array of size [n][target+1]: As there are two changing parameters in the recursive solution, 'ind' and 'target'. The maximum value 'ind' can attain is (n), where n is the size of array and for 'target' only values between 0 to target. Therefore, we need 2D dp array.

The dp array stores the calculations of subproblems. Initialize dp array with -1, to indicate that no subproblem has been solved yet.

While encountering an overlapping subproblem: When we come across a subproblem, for which the dp array has value other than -1, it means we have found a subproblem which has been solved before hence it is an overlapping subproblem. No need to calculate it's value again just retrieve the value from dp array and return it.

Store the value of subproblem: Whenever, a subproblem is enocountered and it is not solved yet(the value at this index will be -1 in the dp array), store the calculated value of subproblem in the array.

#include <bits/stdc++.h>
using namespace std;

class Solution{
private:
    /* Function to check if there is a subset of arr
    with a sum equal to 'target' using memoization*/
    bool func(int ind, int target, vector<int>& arr, vector<vector<int>>& dp) {
        // Base cases
        if (target == 0)
            return true;

        if (ind == 0)
            return arr[0] == target;
            
        /* If the result for this subproblem has 
        already been computed, return it*/
        if (dp[ind][target] != -1)
            return dp[ind][target];

        // Try not taking the current element into subset
        bool notTaken = func(ind - 1, target, arr, dp);

        /* Try taking the current element into the 
        subset if it doesn't exceed the target*/
        bool taken = false;
        if (arr[ind] <= target)
            taken = func(ind - 1, target - arr[ind], arr, dp);

        /* Store the result in the dp
        array to avoid recomputation*/
        return dp[ind][target] = notTaken || taken;
    }
public:
    /* Function to check if there is a subset
    of 'arr' with a sum equal to 'target'*/
    bool isSubsetSum(vector<int>& arr, int target) {
        // Initialize a 2D DP array for memoization
        vector<vector<int>> dp(arr.size(), vector<int>(target + 1, -1));
        
        // Return the result
        return func(arr.size() - 1, target, arr, dp);
    }
};
int main() {
    vector<int> arr = {1, 2, 3, 4};
    int target = 4;

    //Create an instance of Solution class
    Solution sol;
    
    // Call the subsetSumToK function and print the result
    if (sol.isSubsetSum(arr, target))
        cout << "Subset with the given target found";
    else
        cout << "Subset with the given target not found";

    return 0;
}
import java.util.*;

class Solution {
    /* Function to check if there is a subset of
    arr with sum equal to 'target' using memoization*/
    private boolean func(int ind, int target, int[] arr, int[][] dp) {
        // Base cases
        if (target == 0)
            return true;
        
        if (ind == 0)
            return arr[0]== target;
            
        /* If the result for this subproblem has 
        already been calculated, return it*/
        if (dp[ind][target] != -1)
            return dp[ind][target] == 0 ? false : true;
        
        // Try not taking the current element into subset
        boolean notTaken = func(ind - 1, target, arr, dp);
        
        /* Try taking the current element into the
        subset if it doesn't exceed the target*/
        boolean taken = false;
        if (arr[ind] <= target)
            taken = func(ind - 1, target - arr[ind], arr, dp);
        
        /* Store the result in the DP table and 
        return whether either option was successful*/
        dp[ind][target] = notTaken || taken ? 1 : 0;
        return notTaken || taken;
    }
    
    /* Function to check if there is a subset
    of 'arr' with sum equal to 'target'*/
    public boolean isSubsetSum(int[] arr, int target) {
        // Declare a DP table with dimensions [n][k+1]
        int dp[][] = new int[arr.length][target + 1];
        
        // Initialize DP table with -1 
        for (int row[] : dp)
            Arrays.fill(row, -1);
            
        // Return the result
        return func(arr.length - 1, target, arr, dp);
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4};
        int target = 4;
        
        // Create an instance of Solution class
        Solution sol = new Solution();
        
        // Call the isSubsetSum function and print the result
        if (sol.isSubsetSum(arr, target))
            System.out.println("Subset with the given target found");
        else
            System.out.println("Subset with the given target not found");
    }
}
class Solution:
    """ Function to check if there is a subset of arr
    with sum equal to 'target' using memoization"""
    def func(self, ind, target, arr, dp):
        # Base cases
        if target == 0:
            return True
        
        if ind == 0:
            return arr[0] == target
            
        """ Check if the result for this combination of 
        'ind' and 'target' has already been computed"""
        if dp[ind][target] != -1:
            return dp[ind][target]
        
        # Try not taking the current element into subset
        notTaken = self.func(ind - 1, target, arr, dp)
        
        """ Try taking the current element into the
        subset if it doesn't exceed the target"""
        taken = False
        if arr[ind] <= target:
            taken = self.func(ind - 1, target - arr[ind], arr, dp)
        
        # Return the result
        return notTaken or taken
    
    """ Function to check if there is a subset
    of 'arr' with sum equal to 'target'"""
    def isSubsetSum(self, arr, target):
        # Initialize a memoization table with -1.
        dp = [[-1 for j in range(target + 1)] for i in range(len(arr))]
        
        # Return the result
        return self.func(len(arr) - 1, target, arr, dp)
    
if __name__ == "__main__":
    arr = [1, 2, 3, 4]
    target = 4
    
    # Create an instance of Solution class
    sol = Solution()
    
    # Call the isSubsetSum function and print the result
    if sol.isSubsetSum(arr, target):
        print("Subset with the given target found")
    else:
        print("Subset with the given target not found")
class Solution {
    /* Function to check if there is a subset of arr
    with sum equal to 'target' using memoization*/
    func(ind, target, arr, dp) {
        // Base cases
        if (target === 0)
            return true;
        
        if (ind === 0)
            return arr[0] === target;
            
        /* If the result for this subproblem has 
        already been calculated, return it*/
        if (dp[ind][target] != -1)
            return dp[ind][target] == 0 ? false : true;
        
        // Try not taking the current element into subset
        let notTaken = this.func(ind - 1, target, arr, dp);
        
        /* Try taking the current element into the
        subset if it doesn't exceed the target*/
        let taken = false;
        if (arr[ind] <= target)
            taken = this.func(ind - 1, target - arr[ind], arr, dp);
        
        // Return the result
        return dp[ind][target] = notTaken || taken;
    }
    
    /* Function to check if there is a subset
    of 'arr' with sum equal to 'target'*/
    isSubsetSum(arr, target) {
        /* Initialize a 2D array 'dp' 
        to memoize subproblem results*/
        const dp = new Array(arr.length);
        for (let i = 0; i < arr.length; i++) {
            dp[i] = new Array(target + 1).fill(-1);
        }
        // Return the result
        return this.func(arr.length - 1, target, arr, dp);
    }
}

let arr = [1, 2, 3, 4];
let target = 4;

// Create an instance of Solution class
let sol = new Solution();

// Call the isSubsetSum function and print the result
if (sol.isSubsetSum(arr, target))
    console.log("Subset with the given target found");
else
    console.log("Subset with the given target not found");

Complexity Analysis:

Time Complexity: O(N*target), There are 'N*target' states therefore at max ‘N*target’ new problems will be solved.

Space Complexity:O(N*target) + O(N), As we are using a recursion stack space(O(N)) and a 2D array ( O(N*target)).

In order to convert a recursive code to tabulation code, we try to convert the recursive code to tabulation and here are the steps:

Declare a dp array of size [n][target+1]: As there are two changing parameters in the recursive solution, 'ind' and 'target'. The maximum value 'ind' can attain is (n) and including 0 its n, where n is the size of array, for 'target' can have any values between 0 to 'target'. So we need a 2D dp array. Set its type as bool and initialize it as false.

Setting Base Cases in the Array: In the recursive code, our base condition was when target == 0, it means the required subset is found and we were returning true. So, set 'true' in the dp array for every index where target = 0.

The first row dp[0][] indicates that only the first element of the array is considered, therefore for the target value equal to arr[0], only cell with that target will be true, so explicitly set dp[0][arr[0]] =true, (dp[0][arr[0]] means that we are considering the first element of the array with the target equal to the first element itself). Please note that it can happen that arr[0]>target, so we first check it: if(arr[0]<=target) then set dp[0][arr[0]] = true.

Iterative Computation Using Loops: Initialize two nested for loops to traverse the dp array and following the logic discussed in the recursive approach, set the value of each cell in the 2D dp array. Instead of recursive calls, use the dp array itself to find the values of intermediate calculations.

Returning the answer: At last dp[n-1][target] will hold the solution after the completion of whole process, as we are doing the calculations in bottom-up manner.

#include <bits/stdc++.h>
using namespace std;

class Solution{
private:
    /* Function to check if there is a 
    subset of 'arr' with a sum equal to 'k'*/
    bool func(int n, int target, vector<int> &arr) {
        /* Initialize a 2D DP array with dimensions
        (n x target+1) to store subproblem results*/
        vector<vector<bool>> dp(n, vector<bool>(target + 1, false));

        // Base case(when target = 0)
        for (int i = 0; i < n; i++) {
            dp[i][0] = true;
        }

        /* Base case (If the first element of 'arr' is less
        than or equal to 'target', set dp[0][arr[0]] to true)*/
        if (arr[0] <= target) {
            dp[0][arr[0]] = true;
        }

        // Fill the DP array iteratively
        for (int ind = 1; ind < n; ind++) {
            for (int i = 1; i <= target; i++) {
                 
                /* If we don't take the current element, the 
                result is the same as the previous row*/
                bool notTaken = dp[ind - 1][target];

                /* If we take the current element, subtract its
                value from the target and check the previous row*/
                bool taken = false;
                if (arr[ind] <= target) {
                    taken = dp[ind - 1][target - arr[ind]];
                }

                /* Store the result in the DP 
                array for the current subproblem*/
                dp[ind][target] = notTaken || taken;
            }
        }

        // The final result is stored in dp[n-1][k]
        return dp[n - 1][target];
}
public:
    /*Function to check if there is a subset
    of 'arr' with sum equal to 'target'*/
    int isSubsetSum(vector<int> arr, int target){
        //Return the result
        return func(arr.size(), target, arr);
    }
};
int main() {
    vector<int> arr = {1, 2, 3, 4};
    int target = 4;

    //Create an instance of Solution class
    Solution sol;
    
    // Call the function and print the result
    if (sol.isSubsetSum(arr, target))
        cout << "Subset with the given target found";
    else
        cout << "Subset with the given target not found";

    return 0;
}
import java.util.*;

class Solution {
    /* Function to check if there is a subset
    of 'arr' with sum equal to 'target'*/
    private boolean func(int n, int target, int[] arr) {
        /* Initialize a 2D DP array with dimensions 
        (n x target+1) to store subproblem results*/
        boolean[][] dp = new boolean[n][target + 1];

        // Base case (when target = 0)
        for (int i = 0; i < n; i++) {
            dp[i][0] = true;
        }

        /* Base case (If the first element of 
        'arr' is less than or equal to 'target')*/
        if (arr[0] <= target) {
            dp[0][arr[0]] = true;
        }

        // Fill the DP array iteratively
        for (int ind = 1; ind < n; ind++) {
            for (int i = 1; i <= target; i++) {
                /* If we don't take the current element, the 
                result is the same as the previous row*/
                boolean notTaken = dp[ind - 1][i];

                /* If we take the current element, subtract its
                value from the target and check the previous row*/
                boolean taken = false;
                if (arr[ind] <= i) {
                    taken = dp[ind - 1][i - arr[ind]];
                }

                /* Store the result in the DP 
                array for the current subproblem*/
                dp[ind][i] = notTaken || taken;
            }
        }

        // The final result is stored in dp[n-1][target]
        return dp[n - 1][target];
    }

    /* Function to check if there is a subset
    of 'arr' with sum equal to 'target'*/
    public boolean isSubsetSum(int[] arr, int target) {
        // Return the result
        return func(arr.length, target, arr);
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4};
        int target = 4;

        // Create an instance of Solution class
        Solution sol = new Solution();

        // Call the isSubsetSum function and print the result
        if (sol.isSubsetSum(arr, target))
            System.out.println("Subset with the given target found");
        else
            System.out.println("Subset with the given target not found");
    }
}
class Solution:
    """ Function to check if there is a subset
    of 'arr' with sum equal to 'target'"""
    def func(self, n, target, arr):
        """ Initialize a 2D DP array with dimensions
        (n x target+1) to store subproblem results"""
        dp = [[False] * (target + 1) for _ in range(n)]

        # Base case (when target = 0)
        for i in range(n):
            dp[i][0] = True

        """ Base case (If the first element of 'arr'
        is less than or equal to 'target')"""
        if arr[0] <= target:
            dp[0][arr[0]] = True

        # Fill the DP array iteratively
        for ind in range(1, n):
            for i in range(1, target + 1):
                """ If we don't take the current element, the
                result is the same as the previous row"""
                notTaken = dp[ind - 1][i]

                """ If we take the current element, subtract its
                value from the target and check the previous row"""
                taken = False
                if arr[ind] <= i:
                    taken = dp[ind - 1][i - arr[ind]]

                """ Store the result in the DP 
                array for the current subproblem"""
                dp[ind][i] = notTaken or taken

        # The final result is stored in dp[n-1][target]
        return dp[n - 1][target]

    """ Function to check if there is a subset
    of 'arr' with sum equal to 'target'"""
    def isSubsetSum(self, arr, target):
        # Return the result
        return self.func(len(arr), target, arr)

if __name__ == "__main__":
    arr = [1, 2, 3, 4]
    target = 4
    
    # Create an instance of Solution class
    sol = Solution()
    
    # Call the isSubsetSum function and print the result
    if sol.isSubsetSum(arr, target):
        print("Subset with the given target found")
    else:
        print("Subset with the given target not found")
class Solution {
    /* Function to check if there is a subset 
    of 'arr' with a sum equal to 'target'*/
    func(n, target, arr) {
        /* Initialize a 2D DP array with dimensions
        (n x target+1) to store subproblem results*/
        let dp = new Array(n).fill(null).map(() => new Array(target + 1).fill(false));
        
        // Base case (when target = 0)
        for (let i = 0; i < n; i++) {
            dp[i][0] = true;
        }
        
        /* Base case (If the first element of 
        'arr' is less than or equal to 'target')*/
        if (arr[0] <= target) {
            dp[0][arr[0]] = true;
        }
        
        // Fill the DP array iteratively
        for (let ind = 1; ind < n; ind++) {
            for (let i = 1; i <= target; i++) {
                /* If we don't take the current element, the
                result is the same as the previous row*/
                let notTaken = dp[ind - 1][i];
                
                /* If we take the current element, subtract its 
                value from the target and check the previous row*/
                let taken = false;
                if (arr[ind] <= i) {
                    taken = dp[ind - 1][i - arr[ind]];
                }
                
                /* Store the result in the DP 
                array for the current subproblem*/
                dp[ind][i] = notTaken || taken;
            }
        }
        
        // The final result is stored in dp[n-1][target]
        return dp[n - 1][target];
    }
    
    /* Function to check if there is a subset
    of 'arr' with sum equal to 'target'*/
    isSubsetSum(arr, target) {
        // Return the result
        return this.func(arr.length, target, arr);
    }
}

let arr = [1, 2, 3, 4];
let target = 4;

// Create an instance of Solution class
let sol = new Solution();

// Call the isSubsetSum function and print the result
if (sol.isSubsetSum(arr, target))
    console.log("Subset with the given target found");
else
    console.log("Subset with the given target not found");

Complexity Analysis:

Time Complexity: O(N*target), As, here are three nested loops that account for O(N*target) complexity.

Space Complexity:O(N*target), As a 2D array of size N*target is used.

If we observe the relation obtained in the tabulation, dp[ind][target] = dp[ind-1][target] || dp[ind-1][target-arr[ind]]. We see that to calculate a value of a cell of the dp array, we need only the previous row values (say prev). So, we don’t need to store an entire array. Hence we can space optimize it.

Steps to space optimize the tabulation approach:

Decalre an array to store the previous row of the DP table. Initialize the first row and first column of the DP table based on the base conditions discussed in tabulation.
Now, initiate two nested loops in bottom-up approach. The first loop will run for 'ind' and the second loop will run for the 'target' variable.
In order to store the current row of the DP table, initialize a new array 'cur' and fill the first cell to 'true' for base condition.
Do the calculations for 'cur' row by performing the pick/non-pick technique used in previous approaches.
Now, update the previous row with the current row for the next iteration and at last return the final result stored in the last cell of the previous row(prev[k]).

#include <bits/stdc++.h>
using namespace std;

class Solution{
private:
    /* Function to check if there is a subset
    of 'arr' with a sum equal to 'target'*/
    bool func(int n, int target, vector<int> &arr) {
        /* Initialize a vector 'prev' to store
        the previous row of the DP table*/
        vector<bool> prev(target + 1, false);

        /* Base case: If the target sum is 0, we
        can always achieve it by taking no elements*/
        prev[0] = true;

        /* Base case: If the first element of 'arr' is less
        than or equal to 'target', set prev[arr[0]] to true*/
        if (arr[0] <= target) {
            prev[arr[0]] = true;
        }

        /* Iterate through the elements 
        of 'arr' and update the DP table*/
        for (int ind = 1; ind < n; ind++) {
            /* Initialize a new row 'cur' to store
            the current state of the DP table*/
            vector<bool> cur(target + 1, false);

            /* Base case: If the target sum is 0,
            we can achieve it by taking no elements*/
            cur[0] = true;

            for (int i = 1; i <= target; i++) {
                /* If we don't take the current element, the
                result is the same as the previous row*/
                bool notTaken = prev[i];

                /* If we take the current element, subtract its 
                value from the target and check the previous row*/
                bool taken = false;
                if (arr[ind] <= i) {
                    taken = prev[i - arr[ind]];
                }

                /* Store the result in the current DP 
                table row for the current subproblem*/
                cur[i] = notTaken || taken;
            }

            /* Update 'prev' with the curren
            t row 'cur' for the next iteration*/
            prev = cur;
        }

        // The final result is stored in prev[target]
        return prev[target];
    }
public:
    /* Function to check if there is a subset
    of 'arr' with a sum equal to 'target'*/
    int isSubsetSum(vector<int> &arr, int target){
        //Return the result
        return func(arr.size(), target, arr);
    }
};
int main() {
    vector<int> arr = {1, 2, 3, 4};
    int target = 4;
    
    //Create an instance of Solution class
    Solution sol;

    // Call the function and print the result
    if (sol.isSubsetSum(arr, target))
        cout << "Subset with the given target found";
    else
        cout << "Subset with the given target not found";

    return 0;
}

import java.util.*;

class Solution {
    /* Function to check if there is a subset
    of 'arr' with a sum equal to 'target'*/
    private boolean func(int n, int target, int[] arr) {
        /* Initialize an array 'prev' to store
        the previous row of the DP table*/
        boolean[] prev = new boolean[target + 1];
        
        /* Base case: If the target sum is 0, we 
        can always achieve it by taking no elements*/
        prev[0] = true;
        
        /* Base case: If the first element of 
        'arr' is less than or equal to 'target'*/
        if (arr[0] <= target) {
            prev[arr[0]] = true;
        }
        
        /* Iterate through the elements
        of 'arr' and update the DP table*/
        for (int ind = 1; ind < n; ind++) {
            /* Initialize a new array 'cur' to store
            the current state of the DP table*/
            boolean[] cur = new boolean[target + 1];
            
            /* Base case: If the target sum is 0, we 
            can achieve it by taking no elements*/
            cur[0] = true;
            
            for (int i = 1; i <= target; i++) {
                /* If we don't take the current element, the 
                result is the same as the previous row*/
                boolean notTaken = prev[i];
                
                /* If we take the current element, subtract its
                value from the target and check the previous row*/
                boolean taken = false;
                if (arr[ind] <= i) {
                    taken = prev[i - arr[ind]];
                }
                
                /* Store the result in the current DP
                table row for the current subproblem*/
                cur[i] = notTaken || taken;
            }
            
            /* Update 'prev' with the current 
            row 'cur' for the next iteration*/
            prev = cur;
        }
        
        // The final result is stored in prev[target]
        return prev[target];
    }
    
    /* Function to check if there is a subset 
    of 'arr' with sum equal to 'target'*/
    public boolean isSubsetSum(int[] arr, int target) {
        // Return the result
        return func(arr.length, target, arr);
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4};
        int target = 4;
        
        // Create an instance of Solution class
        Solution sol = new Solution();
        
        // Call the isSubsetSum function and print the result
        if (sol.isSubsetSum(arr, target))
            System.out.println("Subset with the given target found");
        else
            System.out.println("Subset with the given target not found");
    }
}
class Solution:
    """ Function to check if there is a subset
    of 'arr' with a sum equal to 'target'"""
    def func(self, n, target, arr):
        """ Initialize an array 'prev' to store
        the previous row of the DP table"""
        prev = [False] * (target + 1)
        
        """ Base case: If the target sum is 0, we
        can always achieve it by taking no elements"""
        prev[0] = True
        
        """ Base case: If the first element of  
        'arr' is less than or equal to 'target'"""
        if arr[0] <= target:
            prev[arr[0]] = True
        
        """ Iterate through the elements of
        'arr' and update the DP table"""
        for ind in range(1, n):
            """ Initialize a new array 'cur' to store
            the current state of the DP table"""
            cur = [False] * (target + 1)
            
            """ Base case: If the target sum is 0, 
            we can achieve it by taking no elements"""
            cur[0] = True
            
            for i in range(1, target + 1):
                """ If we don't take the current element, the
                result is the same as the previous row"""
                notTaken = prev[i]
                
                """ If we take the current element, subtract its 
                value from the target and check the previous row"""
                taken = False
                if arr[ind] <= i:
                    taken = prev[i - arr[ind]]
                
                """ Store the result in the current DP 
                table row for the current subproblem"""
                cur[i] = notTaken or taken
            
            """ Update 'prev' with the current 
            row 'cur' for the next iteration"""
            prev = cur
        
        # The final result is stored in prev[target]
        return prev[target]
    
    """ Function to check if there is a subset
    of 'arr' with sum equal to 'target'"""
    def isSubsetSum(self, arr, target):
        # Return the result
        return self.func(len(arr), target, arr)
    
if __name__ == "__main__":
    arr = [1, 2, 3, 4]
    target = 4
    
    # Create an instance of Solution class
    sol = Solution()
    
    # Call the isSubsetSum function and print the result
    if sol.isSubsetSum(arr, target):
        print("Subset with the given target found")
    else:
        print("Subset with the given target not found")
class Solution {
    /* Function to check if there is a subset
    of 'arr' with a sum equal to 'target'*/
    func(n, target, arr) {
        /* Initialize an array 'prev' to store
        the previous row of the DP table*/
        let prev = new Array(target + 1).fill(false);
        
        /* Base case: If the target sum is 0, we
        can always achieve it by taking no elements*/
        prev[0] = true;
        
        /* Base case: If the first element of 
        'arr' is less than or equal to 'target'*/
        if (arr[0] <= target) {
            prev[arr[0]] = true;
        }
        
        /* Iterate through the elements of 
        'arr' and update the DP table*/
        for (let ind = 1; ind < n; ind++) {
            /* Initialize a new array 'cur' to store
            the current state of the DP table*/
            let cur = new Array(target + 1).fill(false);
            
            /* Base case: If the target sum is 0,
            we can achieve it by taking no elements*/
            cur[0] = true;
            
            for (let i = 1; i <= target; i++) {
                /* If we don't take the current element, the
                result is the same as the previous row*/
                let notTaken = prev[i];
                
                /* If we take the current element, subtract its 
                value from the target and check the previous row*/
                let taken = false;
                if (arr[ind] <= i) {
                    taken = prev[i - arr[ind]];
                }
                
                /* Store the result in the current DP
                table row for the current subproblem*/
                cur[i] = notTaken || taken;
            }
            
            /* Update 'prev' with the current
            row 'cur' for the next iteration*/
            prev = cur;
        }
        
        // The final result is stored in prev[target]
        return prev[target];
    }
    
    /* Function to check if there is a subset
    of 'arr' with sum equal to 'target'*/
    isSubsetSum(arr, target) {
        // Return the result
        return this.func(arr.length, target, arr);
    }
}

// Main function
let arr = [1, 2, 3, 4];
let target = 4;

// Create an instance of Solution class
let sol = new Solution();

if (sol.isSubsetSum(arr, target)) {
    console.log("Subset with given target found");
} else {
    console.log("Subset with given target not found");
}

Complexity Analysis:

Time Complexity: O(N*target), As, here are three nested loops that account for O(N*target) complexity.

Space Complexity:O(target), As we are using two external arrays of size ‘target'.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Steps to form the recursive solution:

Complexity Analysis:

Complexity Analysis:

Steps to space optimize the tabulation approach:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code