36373839404142434445464748

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 to take 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");
    }
}

123456789101112131415161718192021222324252627282930313233343536373839404142

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 to take 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")

1234567891011