InterviewBit Academy is now Scaler!
Learn Tech Skills from Scratch @ Scaler EDGE

Subset Sum Problem!

Problem Description

Given an integer array A of size N.

You are also given an integer B, you need to find whether their exist a subset in A whose sum equal B.

If there exist a subset then return 1 else return 0.

Problem Constraints

1 <= N <= 100

1 <= A[i] <= 100

1 <= B <= 105

Input Format

First argument is an integer array A.

Second argument is an integer B.

Output Format

Return 1 if there exist a subset with sum B else return 0.

Example Input

Input 1:

 A = [3, 34, 4, 12, 5, 2]
 B = 9

Input 2:

 A = [3, 34, 4, 12, 5, 2]
 B = 30

Example Output

Output 1:


Output 2:


Example Explanation

Explanation 1:

 There is a subset (4, 5) with sum 9.

Explanation 2:

 There is no subset that add up to 30.

NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Subset Sum Problem! on Interview Code Editor
Sign Up
to access hints and editorial solutions for Subset Sum Problem!
Asked In:


Click here to start solving coding interview questions