Advertisement
Mishakis

SubsetOfSum

Dec 3rd, 2018
159
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.18 KB | None | 0 0
  1. import java.io.ByteArrayInputStream;
  2. import java.util.Scanner;
  3.  
  4. public class SubsetOfSumS {
  5.     static boolean subsetSum(int[] set, int index, int sum) {
  6.         if (sum == 0) {
  7.             return true;
  8.         }
  9.         if (sum < 0 || index >= set.length) {
  10.             return false;
  11.         }
  12.  
  13.         return subsetSum(set, index + 1, sum - set[index]) ||
  14.                 subsetSum(set, index + 1, sum);
  15.     }
  16.  
  17.     static void testInput() {
  18.         String test = "14\n" +
  19.                 "2 1 2 4 3 5 2 6";
  20.         System.setIn(new ByteArrayInputStream(test.getBytes()));
  21.     }
  22.  
  23.  
  24.     public static void main(String[] args) {
  25.         testInput();
  26.         Scanner scanner = new Scanner(System.in);
  27.         int sum = scanner.nextInt();
  28.         scanner.nextLine();
  29.         String[] setAsString = scanner.nextLine().split(" +");
  30.         int[] set = new int[setAsString.length];
  31.         for (int i = 0; i < set.length; i++) {
  32.             set[i] = Integer.parseInt(setAsString[i]);
  33.         }
  34.  
  35.         if(subsetSum(set, 0, sum) == true)
  36.         {
  37.             System.out.println("yes");
  38.         }
  39.         else
  40.         {
  41.             System.out.println("no");
  42.         }
  43.     }
  44. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement