int answer;
// Returns true if there is a subset of set[] with sun equal to given sum
int isSubsetSum(int set[], int n, int sum)
{
   // Base Cases
   if (sum == 0) {
   	 answer++;
     return 0; //return false here as we are after all the sums
   }
   if (n == 0 && sum != 0)
     return 0;
 
   // 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
int main()
{
  int set[] = {3, 34, 4, 12, 5, 2};
  int sum = 9;
  int n = sizeof(set)/sizeof(set[0]);
  isSubsetSum(set, n, sum);
  printf("total %d\n", answer);
  return 0;
}

aW50IGFuc3dlcjsKLy8gUmV0dXJucyB0cnVlIGlmIHRoZXJlIGlzIGEgc3Vic2V0IG9mIHNldFtdIHdpdGggc3VuIGVxdWFsIHRvIGdpdmVuIHN1bQppbnQgaXNTdWJzZXRTdW0oaW50IHNldFtdLCBpbnQgbiwgaW50IHN1bSkKewogICAvLyBCYXNlIENhc2VzCiAgIGlmIChzdW0gPT0gMCkgewogICAJIGFuc3dlcisrOwogICAgIHJldHVybiAwOyAvL3JldHVybiBmYWxzZSBoZXJlIGFzIHdlIGFyZSBhZnRlciBhbGwgdGhlIHN1bXMKICAgfQogICBpZiAobiA9PSAwICYmIHN1bSAhPSAwKQogICAgIHJldHVybiAwOwogCiAgIC8vIElmIGxhc3QgZWxlbWVudCBpcyBncmVhdGVyIHRoYW4gc3VtLCB0aGVuIGlnbm9yZSBpdAogICBpZiAoc2V0W24tMV0gPiBzdW0pCiAgICAgcmV0dXJuIGlzU3Vic2V0U3VtKHNldCwgbi0xLCBzdW0pOwogCiAgIC8qIGVsc2UsIGNoZWNrIGlmIHN1bSBjYW4gYmUgb2J0YWluZWQgYnkgYW55IG9mIHRoZSBmb2xsb3dpbmcKICAgICAgKGEpIGluY2x1ZGluZyB0aGUgbGFzdCBlbGVtZW50CiAgICAgIChiKSBleGNsdWRpbmcgdGhlIGxhc3QgZWxlbWVudCAgICovCiAgIHJldHVybiBpc1N1YnNldFN1bShzZXQsIG4tMSwgc3VtKSB8fCBpc1N1YnNldFN1bShzZXQsIG4tMSwgc3VtLXNldFtuLTFdKTsKfQogCi8vIERyaXZlciBwcm9ncmFtIHRvIHRlc3QgYWJvdmUgZnVuY3Rpb24KaW50IG1haW4oKQp7CiAgaW50IHNldFtdID0gezMsIDM0LCA0LCAxMiwgNSwgMn07CiAgaW50IHN1bSA9IDk7CiAgaW50IG4gPSBzaXplb2Yoc2V0KS9zaXplb2Yoc2V0WzBdKTsKICBpc1N1YnNldFN1bShzZXQsIG4sIHN1bSk7CiAgcHJpbnRmKCJ0b3RhbCAlZFxuIiwgYW5zd2VyKTsKICByZXR1cm4gMDsKfQ==