Write a recursive solution to solve the Partition problem. Partition: Given a se

Question

Write a recursive solution to solve the Partition problem. Partition: Given a set A of n integers a, a, .....a., can you find a subset A_1 of integers such that the sum of the Integers in A_1 is half of the Sum of all the n Integers (that Is, sigma_alpha 1 A_1 a_i)? Input: 1.Number of integers of set A: n 2.n Integers: a_1 a_2, a_n. Output: Print out yes if you can find a subset A_1 of integers such that the sum of the integers in A_1 is half of the sum of all the n integers (that is, sigma_a is A a_1); otherwise, print out no. Test your program with the following two instances: 1) 5 integers. 5, 10, 6, 8, 1 2) 20 integers: 1, 5, 7. 34. 76, 54, 23, 19, 22, 81, 44, 77, 29, 40, 11, 42, 43, 31, 57. 61

Explanation / Answer

// C code to determine if there exist a subset such that sum of elemnets of subset is half of sum of total set
#include <stdio.h>
#include <stdbool.h>

bool partitionSum(int array[], int size, int subsetSum)
{
  
int i,j;
// result[i][j] = 1 if there is a array[0..j-1] with sum = i
bool result[subsetSum+1][size+1];

// If subsetSum is 0, then answer is 1
for (i = 0; i <= size; i++) result[0][i] = 1;

// If subsetSum is not 0 and array is empty, then answer is 0
for (i = 1; i <= subsetSum; i++)
result[i][0] = 0;

// filling the result table
for (i = 1; i <= subsetSum; i++)
{
for (j = 1; j <= size; j++)
{
result[i][j] = result[i][j-1];
if (i >= array[j-1])
result[i][j] = result[i][j] || result[i - array[j-1]][j-1];
}
}

// return the value of subsetSum,size in result table
return result[subsetSum][size];
}

int main()
{
int i,sum = 0;

int array1[] = {5, 10, 6, 8, 1};
int n = sizeof(array1)/sizeof(array1[0]);
  
for (i = 0; i < n; ++i)
{
sum = sum + array1[i];
}
  
int subsetSum = sum/2;
  
if (partitionSum(array1, n, subsetSum) == 1)
printf("Yes, Subset exist ");
else
printf("Subset does not exist ");
// output: Yes, Subset exist

sum = 0;

int array2[] = {1, 5, 7, 34, 76, 54, 23, 19, 22, 81, 44, 77, 29, 40, 11, 42, 43, 31, 57, 61};
n = sizeof(array2)/sizeof(array2[0]);
  
for (i = 0; i < n; ++i)
{
sum = sum + array2[i];
}
  
subsetSum = sum/2;

if (partitionSum(array2, n, subsetSum) == 1)
printf("Yes, Subset exist ");
else
printf("Subset does not exist ");
// output: Yes, Subset exist

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.