{"id":27159,"date":"2018-01-03T21:57:58","date_gmt":"2018-01-03T16:27:58","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27159"},"modified":"2018-01-03T21:57:58","modified_gmt":"2018-01-03T16:27:58","slug":"c-programming-subset-sum-problem","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-subset-sum-problem\/","title":{"rendered":"C 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
 
 C<\/span> <\/div> 
\/\/ A recursive solution for subset sum problem#include <stdio.h> \/\/ Returns true if there is a subset of set[] with sun equal to given sumbool 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 functionint main(){  int set[] = {3, 34, 4, 12, 5, 2};  int sum = 9;  int n = sizeof(set)\/sizeof(set[0]);  if (isSubsetSum(set, n, sum) == true)     printf("Found a subset with given sum");  else     printf("No subset with given sum");  return 0;}<\/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
 
 C<\/span> <\/div> 
\/\/ A Dynamic Programming solution for subset sum problem#include <stdio.h> \/\/ Returns true if there is a subset of set[] with sun equal to given sumbool 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    bool subset[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 functionint main(){  int set[] = {3, 34, 4, 12, 5, 2};  int sum = 9;  int n = sizeof(set)\/sizeof(set[0]);  if (isSubsetSum(set, n, sum) == true)     printf("Found a subset with given sum");  else     printf("No subset with given sum");  return 0;}<\/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":"
C 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":[69969,69866,1,70145],"tags":[72852,72855,80976,80977,70593,70616,80973,80974,74496],"class_list":["post-27159","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-c-programming","category-coding","category-dynamic-programming","tag-problems-on-dynamic-programming","tag-simple-dynamic-programming-example","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-in-c","tag-subset-sum-problem-in-java-find-all-subsets-that-sum-to-a-particular-value","tag-sum-of-subset-problem-using-backtracking"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27159","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=27159"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27159\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27159"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27159"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27159"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}