fork(1) download 
  1. class SubsetSum{
  2. 	public static void main(String[] args){
  3. 		int[] arr=new int[]{ -7, -3, -2, 5, 8};
  4. 		System.out.println(solve(arr,0));
  5. 	}
  6. 	public static boolean solve(int[] numbers, int target) {
  7.  
  8. 	    //Safeguard against invalid parameters
  9. 	    if ((target < 0) || (sum(numbers) < target)){
  10. 	        return false;
  11. 	    }
  12.  
  13. 	    boolean [][] table = new boolean [target + 1] [numbers.length + 1]  ;
  14.  
  15. 	    for (int i = 0; i <= numbers.length; ++i) {
  16. 	        table[0][i] = true;
  17. 	    }
  18.  
  19. 	    /* Base cases have been covered. 
  20. 	     * Now look set subsets [1..n][target] to be true or false.
  21. 	     * n represents the number of elements from the start that have a subset 
  22. 	     * that sums to target
  23. 	     */
  24.  
  25. 	    for (int i = 1; i <= target; ++i){
  26. 	        for (int j = 1; j <= numbers.length; ++j){
  27. 	            /* Mark index j as one of the numbers in the array
  28. 	             *  which is part of the solution with the given subtarget */
  29. 	            table [i][j] = table[i][j-1];
  30. 	            if (i >= numbers[j-1])
  31. 	                table[i][j] = table[i][j] || table[i - numbers[j-1]] [j-1];
  32. 	        }
  33. 	    }
  34.  
  35. 	    return table[target][numbers.length];
  36. 	}
  37. 	private static int sum(int[] numbers) {
  38. 		int s=0;
  39. 		for(int i:numbers){
  40. 			s+=i;
  41. 		}
  42. 		return s;
  43. 	}
  44. }
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin 
Standard input is empty
stdout 
true
https://ideone.com/OlOG16
language:
Java (HotSpot 12)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!