{"id":27160,"date":"2018-01-03T21:55:05","date_gmt":"2018-01-03T16:25:05","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27160"},"modified":"2018-01-03T21:55:05","modified_gmt":"2018-01-03T16:25:05","slug":"java-programming-subset-sum-problem","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/java-programming-subset-sum-problem\/","title":{"rendered":"Java Programming – Subset Sum Problem"},"content":{"rendered":"

Given a set of non-negative integers, and a value sum<\/em>, determine if there is a subset of the given set with sum equal to given sum<\/em>.<\/span><\/p>\n

Examples: set[] = {3, 34, 4, 12, 5, 2}, sum = 9\r\nOutput:  True  \/\/There is a subset (4, 5) with sum 9.<\/pre>\n
Let isSubSetSum(int set[], int n, int sum) be the function to find whether there is a subset of set[] with sum equal to sum<\/em>. n is the number of elements in set[].<\/p>\n
The isSubsetSum problem can be divided into two subproblems
\n\u2026a) Include the last element, recur for n = n-1, sum = sum \u2013 set[n-1]\n\u2026b) Exclude the last element, recur for n = n-1.
\nIf any of the above the above subproblems return true, then return true.<\/p>\n[ad type=”banner”]\n
Following is the recursive formula for isSubsetSum() problem.<\/p>\n
isSubsetSum(set, n, sum) = isSubsetSum(set, n-1, sum) || \r\n                           isSubsetSum(set, n-1, sum-set[n-1])\r\nBase Cases:<\/strong>\r\nisSubsetSum(set, n, sum) = false, if sum > 0 and n == 0\r\nisSubsetSum(set, n, sum) = true, if sum == 0 \r\n<\/pre>\n
Following is naive recursive implementation that simply follows the recursive structure mentioned above.<\/p>\n
 
 Java<\/span> <\/div> 
\/\/ A recursive solution for subset sum problemclass subset_sum{    \/\/ Returns true if there is a subset of set[] with sum        \/\/ equal to given sum    static boolean isSubsetSum(int set[], int n, int sum)    {       \/\/ Base Cases       if (sum == 0)         return true;       if (n == 0 && sum != 0)         return false;             \/\/ If last element is greater than sum, then ignore it       if (set[n-1] > sum)         return isSubsetSum(set, n-1, sum);             \/* else, check if sum can be obtained by any of the following          (a) including the last element          (b) excluding the last element   *\/       return isSubsetSum(set, n-1, sum) ||                                    isSubsetSum(set, n-1, sum-set[n-1]);    }    \/* Driver program to test above function *\/    public static void main (String args[])    {          int set[] = {3, 34, 4, 12, 5, 2};          int sum = 9;          int n = set.length;          if (isSubsetSum(set, n, sum) == true)             System.out.println("Found a subset with given sum");          else             System.out.println("No subset with given sum");    }}<\/code><\/pre> <\/div>\n
Output :<\/strong><\/p>\n
 Found a subset with given sum<\/pre>\n
The above solution may try all subsets of given set in worst case. Therefore time complexity of the above solution is exponential. The problem is in-fact NP-Complete (There is no known polynomial time solution for this problem).<\/p>\n[ad type=”banner”]\n
We can solve the problem in Pseudo-polynomial time using Dynamic programming. <\/strong>We create a boolean 2D table subset[][] and fill it in bottom up manner. The value of subset[i][j] will be true if there is a subset of set[0..j-1] with sum equal to i., otherwise false. Finally, we return subset[sum][n]\n
 
 Java<\/span> <\/div> 
\/\/ A Dynamic Programming solution for subset sum problemclass subset_sum{    \/\/ Returns true if there is a subset of set[] with sun equal to given sum    static boolean isSubsetSum(int set[], int n, int sum)    {        \/\/ The value of subset[i][j] will be true if there             \/\/ is a subset of set[0..j-1] with sum equal to i        boolean subset[][] = new boolean[sum+1][n+1];              \/\/ If sum is 0, then answer is true        for (int i = 0; i <= n; i++)          subset[0][i] = true;              \/\/ If sum is not 0 and set is empty, then answer is false        for (int i = 1; i <= sum; i++)          subset[i][0] = false;               \/\/ Fill the subset table in botton up manner         for (int i = 1; i <= sum; i++)         {           for (int j = 1; j <= n; j++)           {             subset[i][j] = subset[i][j-1];             if (i >= set[j-1])               subset[i][j] = subset[i][j] ||                                           subset[i - set[j-1]][j-1];           }         }              \/* \/\/ uncomment this code to print table         for (int i = 0; i <= sum; i++)         {           for (int j = 0; j <= n; j++)              printf ("%4d", subset[i][j]);           printf("\\n");         } *\/               return subset[sum][n];    }    \/* Driver program to test above function *\/    public static void main (String args[])    {          int set[] = {3, 34, 4, 12, 5, 2};          int sum = 9;          int n = set.length;          if (isSubsetSum(set, n, sum) == true)             System.out.println("Found a subset with given sum");          else             System.out.println("No subset with given sum");    }}<\/code><\/pre> <\/div>\n
Output:<\/p>\n
Found a subset with given sum<\/pre>\n
Time complexity of the above solution is O(sum*n).<\/p>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
Java Programming – Subset Sum Problem – Dynamic Programming Given a set of non-negative integers, and a value sum, determine if there is a subset <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1,70145,2139],"tags":[72846,72987,72985,72843,72844,72850,80975,80976,80977,70593,70616,74632,80972,72851],"class_list":["post-27160","post","type-post","status-publish","format-standard","hentry","category-coding","category-dynamic-programming","category-java","tag-dynamic-programming-in-data-structure","tag-dynamic-programming-in-java","tag-dynamic-programming-java","tag-dynamic-programming-problems","tag-dynamic-programming-software","tag-explain-dynamic-programming","tag-subset-sum-calculator","tag-subset-sum-in-c-program","tag-subset-sum-in-java-program","tag-subset-sum-problem","tag-subset-sum-problem-dynamic-programming","tag-subset-sum-problem-java","tag-subset-sum-problem-np-complete","tag-youtube-dynamic-programming"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27160","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27160"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27160\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27160"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27160"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27160"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}