Hi I\'m reposting this question again for the third time now because it wasn\'t

Question

Hi I'm reposting this question again for the third time now because it wasn't properly answered. please help in C++ LANGUAGE WITH THE OUT PUT AND PROPER EXPLANATION write a recursive solution to solve the partition problem. Partition: Given a set A of n integers a 1, a2, an, can you find a subset A1 of integers such that the sum of the integers in A1 is half of the sum of all the n integers (that is, aieAu ai au? Input: 1. Number of integers of set A: n 2. n integers: a1, a2, an. output Print out yes if you can find a subset Ar of integers such that the sum of the integers in A1 is half of the sum of all the n integers (that is, Jaen, au Date au); otherwise, print out no Test your program with the following two instances: 1) 5 integers: 5, 10, 6, 8, 1 31, 57, 61 2) 20 integers: 1, 5, 7, 34, 76, 54, 23, 19, 22, 81, 44, 77, 29, 40, 11, 42, 43,

Explanation / Answer

#include <iostream>
#include <math.h>
using namespace std;
int printPowerSet(int *set, int set_size,int sum)
{
    /*set_size of power set of a set with set_size
      n is (2**n -1)*/
    unsigned int pow_set_size = pow(2, set_size);
    int counter, j;

    /*Run from counter 000..0 to 111..1*/
    for(counter = 0; counter < pow_set_size; counter++)
    {
       int c=0;
      for(j = 0; j < set_size; j++)
       {
          /* Check if jth bit in the counter is set
             If set then pront jth element from set */
          if(counter & (1<<j))
              //cout<<set[j];
              c=c+set[j];
       }
       //cout<<" ";
       if(c==sum/2)return c;
    }
  
    return 0;
}

/*Driver program to test printPowerSet*/
int main()
{
  
    /*
    int set[] = {5,10,6,8,1};
    int i,sum=0;
    for(i=0;i<5;i++)
    {
           sum=sum+set[i];
   }
    */
    int set[] = {1,5,7,34,76,54,23,19,22,81,44,77,29,40,11,42,43,31,57,61};
    int i,sum=0;
    for(i=0;i<20;i++)
    {
           sum=sum+set[i];
   }
  
  
    if(printPowerSet(set, 20,sum)==sum/2)cout<<"Yes ";
    else cout<<"No ";
    //char c;
    //cin>>c;
    return 0;
}

ouput:-

for both inputs yes..

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

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