/* This code is contributed by Avinash Prasad (GitHub : avinash11a) */

// A Dynamic Programming solution for subset

// sum problem

import java.util.Scanner;

class Solution {

// Returns true if there is a subset of

// set[] with sum equal to given sum

static boolean isSubsetSum(int set[],

int n, int sum)

{

// The value of subset[i][j] will be

// true if there is a subset of

// set[0..j-1] with sum equal to i

boolean subset[][] =

new boolean[sum+1][n+1];

// If sum is 0, then answer is true

for (int i = 0; i <= n; i++)

subset[0][i] = true;

// If sum is not 0 and set is empty,

// then answer is false

for (int i = 1; i <= sum; i++)

subset[i][0] = false;

// Fill the subset table in botton

// up manner

for (int i = 1; i <= sum; i++)

{

for (int j = 1; j <= n; j++)

{

subset[i][j] = subset[i][j-1];

if (i >= set[j-1])

subset[i][j] = subset[i][j] ||

subset[i - set[j-1]][j-1];

}

}

/* // uncomment this code to print table

for (int i = 0; i <= sum; i++)

{

for (int j = 0; j <= n; j++)

System.out.println (subset[i][j]);

} */

return subset[sum][n];

}

/* Driver program to test above function */

public static void main (String args[])

{

Scanner s = new Scanner(System.in);

int n; //Number of elements in the set

n = s.nextInt();

int set[] = new int[n];

for(int i=0;i<n;i++)

{

set[i] = s.nextInt();

}

int sum; //number for which the subset needs to be Found

sum = s.nextInt();

if (isSubsetSum(set, n, sum) == true)

System.out.println("Found a subset"

+ " with given sum");

else

System.out.println("No subset with"

+ " given sum");

}

}

/* This code is contributed by Avinash Prasad */