Cacher is the code snippet organizer for pro developers

import java.io.*;
import java.util.*;

class Solution {
  public static void main(String[] args) {
    Solution solution = new Solution();
    int[][]input = {
      {8,4,1,9,15,17,0,90},
      {2,5,7,4},
      {3,4,5,1,2}
    };
    int[] sum = {
      104,6,16
    };
    for(int i=0;i<input.length;i++) {
      System.out.println("Input: " + Arrays.toString(input[i]) + ", Result: " + solution.setExistsWithSum(input[i], sum[i]) + ", DP: " + solution.setExistsWithSumDP(input[i], sum[i]));
   }
  }
  
  public boolean setExistsWithSum(int[] input, int sum){
    if(input == null || input.length < 1) {
      return false; 
    }
    return setExistsWithSum(input, sum, 0);
  }
  
  public boolean setExistsWithSum(int[] input, int sum, int index) {
    if(sum == 0){
      return true;
    }
    if(index >= input.length) {
      return false; 
    }
    //exclude
    boolean exclude = setExistsWithSum(input, sum, index+1);
    if(exclude) return true;
    
    //include
    boolean include = setExistsWithSum(input, sum-input[index], index+1);
    
    return include;
  }
  
  public boolean setExistsWithSumDP(int[] input, int sum) {
    if(input == null || input.length < 1) {
      return false;
    }
    int n = input.length;
    boolean[][] tracker = new boolean[n+1][sum+1];
    //Sum with zero exists
    for(int i=0;i<=n;i++){
      tracker[i][0] = true;
    }
    
    for(int i=1; i<=n; i++){
      for(int j=1; j<=sum; j++) {
        if(j-input[i-1] < 0) {
          tracker[i][j] = tracker[i-1][j];
        } else {
          tracker[i][j] = tracker[i-1][j] || tracker[i-1][j-input[i-1]]; 
        }
      }
    }
    return tracker[n][sum];
  }
  

}