// A c program to determine if sum of subset of an int array is equal to a given number
// With Simulation
#include <stdio.h>
#include <stdbool.h>
bool inArrSubsetOfSum(int arr[], int len, int sum)
{
printf("len = %d sum = %d\n", len, sum);
if (sum == 0)
{
printf("return true\n");
return true;
}
if (len == 0 && sum != 0)
{
printf("return false\n");
return false;
}
if (arr[len-1] > sum)
{
printf("(if) inArrSubsetOfSum(arr, %d, %d)\n", len-1, sum);
return inArrSubsetOfSum(arr, len-1, sum);
}
printf("inArrSubsetOfSum(arr, %d, %d) || inArrSubsetOfSum(arr, %d, %d(arr[len-1]=%d))\n",
len-1, sum, len-1, sum - arr[len-1], arr[len-1]);
return inArrSubsetOfSum(arr, len-1, sum) || inArrSubsetOfSum(arr, len-1, sum - arr[len-1]);
}
int main(void)
{
int arr[] = {1, 6, 5, 14, 3, 4}; // 6 + 4 = 10 (sum)
int sum = 10;
int len = sizeof(arr)/sizeof(arr[0]);
printf("len = %d\n", len);
if (inArrSubsetOfSum(arr, len, sum) == true)
printf("Found");
else
printf("Not found");
return 0;
}
/*
run:
len = 6
len = 6 sum = 10
inArrSubsetOfSum(arr, 5, 10) || inArrSubsetOfSum(arr, 5, 6(arr[len-1]=4))
len = 5 sum = 10
inArrSubsetOfSum(arr, 4, 10) || inArrSubsetOfSum(arr, 4, 7(arr[len-1]=3))
len = 4 sum = 10
(if) inArrSubsetOfSum(arr, 3, 10)
len = 3 sum = 10
inArrSubsetOfSum(arr, 2, 10) || inArrSubsetOfSum(arr, 2, 5(arr[len-1]=5))
len = 2 sum = 10
inArrSubsetOfSum(arr, 1, 10) || inArrSubsetOfSum(arr, 1, 4(arr[len-1]=6))
len = 1 sum = 10
inArrSubsetOfSum(arr, 0, 10) || inArrSubsetOfSum(arr, 0, 9(arr[len-1]=1))
len = 0 sum = 10
return false
len = 0 sum = 9
return false
len = 1 sum = 4
inArrSubsetOfSum(arr, 0, 4) || inArrSubsetOfSum(arr, 0, 3(arr[len-1]=1))
len = 0 sum = 4
return false
len = 0 sum = 3
return false
len = 2 sum = 5
(if) inArrSubsetOfSum(arr, 1, 5)
len = 1 sum = 5
inArrSubsetOfSum(arr, 0, 5) || inArrSubsetOfSum(arr, 0, 4(arr[len-1]=1))
len = 0 sum = 5
return false
len = 0 sum = 4
return false
len = 4 sum = 7
(if) inArrSubsetOfSum(arr, 3, 7)
len = 3 sum = 7
inArrSubsetOfSum(arr, 2, 7) || inArrSubsetOfSum(arr, 2, 2(arr[len-1]=5))
len = 2 sum = 7
inArrSubsetOfSum(arr, 1, 7) || inArrSubsetOfSum(arr, 1, 1(arr[len-1]=6))
len = 1 sum = 7
inArrSubsetOfSum(arr, 0, 7) || inArrSubsetOfSum(arr, 0, 6(arr[len-1]=1))
len = 0 sum = 7
return false
len = 0 sum = 6
return false
len = 1 sum = 1
inArrSubsetOfSum(arr, 0, 1) || inArrSubsetOfSum(arr, 0, 0(arr[len-1]=1))
len = 0 sum = 1
return false
len = 0 sum = 0
return true
Found
*/
