package DynamicProgramming;

public class Sum_Of_Subset {
 public static void main(String[] args){
 
 int[] arr = { 7, 3, 2, 5, 8 };
 int Key = 14;
 
 if (subsetSum(arr, arr.length - 1, Key)) {
 System.out.print("Yes, that sum exists");
 }
 else {
 System.out.print("Nope, that number does not exist");
 }
 }
 public static boolean subsetSum(int[] arr, int num, int Key)
 {
 if (Key == 0) {
 return true;
 }
 if (num < 0 || Key < 0) {
 return false;
 }

 boolean include = subsetSum(arr, num - 1, Key - arr[num]);
 boolean exclude = subsetSum(arr, num - 1, Key);

 return include || exclude;
 }
}