fork download
copy 
  1. class SubsetSumProblem {
  2.  
  3. 	public static void main(String[] args) {
  4. 		int set[] = {12, 34, 4, 3, 5, 2};
  5. 		  int sum = 9;
  6. 		  int n = set.length;
  7. 		  if (isSubsetSum(set, n, sum) == true)
  8. 		     System.out.println("Found a subset with given sum");
  9. 		  else
  10. 			  System.out.println("No subset with given sum");
  11. 	}
  12.  
  13. 	// Returns true if there is a subset of set[] with sun equal to given sum
  14. 	public static boolean isSubsetSum(int set[], int n, int sum)
  15. 	{
  16. 	    // The value of subset[i][j] will be true if there is a subset of set[0..j-1]
  17. 	    //  with sum equal to i
  18. 		boolean subset[][] = new boolean[sum+1][n+1];
  19.  
  20. 	    // If sum is 0, then answer is true
  21. 	    for (int i = 0; i <= n; i++)
  22. 	      subset[0][i] = true;
  23.  
  24. 	    // If sum is not 0 and set is empty, then answer is false
  25. 	    // This is not needed in Java as default value of boolean is false. 
  26. //	    for (int i = 1; i <= sum; i++)
  27. //	      subset[i][0] = false;
  28.  
  29. 	     // Fill the subset table in botton up manner
  30. 	     for (int i = 1; i <= sum; i++)
  31. 	     {
  32. 	       for (int j = 1; j <= n; j++)
  33. 	       {
  34. 	    	   if(subset[i][j-1] == true){
  35. 	    		// it is possible to generate sum "i" from smaller subset itself. 
  36. 	    		// So obviously it can be generated by bigger one. So no need to think more
  37. 	    		subset[i][j] = true;   
  38. 	    	   }else if (i == set[j-1]) {
  39. 	    		   subset[i][j] = true;
  40. 	    	   }else if (i >= set[j-1]) {
  41. 	  	        	 //  sum "i" is bigger than set[j-1]. Lets say  set[j-1] + x = i
  42. 	    		     // So x = i - set[j-1]
  43. 	    		     // Now we need to refer currently populated array to check if "x" can be achieved by first j-1 elements.
  44. 	  	        	 int x = i - set[j-1];
  45. 	  	        	 subset[i][j] = subset[x][j-1];
  46. 	    	   }
  47. 	       }
  48.  
  49. 	     }
  50.  
  51. 	     return subset[sum][n];
  52. 	}
  53.  
  54. }
  55.  
Success #stdin #stdout 0.06s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Found a subset with given sum
https://ideone.com/uUxNgb
language:
Java (HotSpot 12)
created:
10 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!