Question

1. Based upon the pseudocode given in “Background”, solve the three versions of add up to K problems: ◦ all pairs of numbers that add up to K ◦ all triples (set of three) that add up to K ◦ all possible subsets of numbers that add up to K: recursive version is given, you are asked to solve it iteratively. 2. Test the three functions using given test cases. 3. Measure the running time of algorithms under various input sizes.

#include <iostream>
#include <bitset>
#include <vector>
#include <time.h>
using namespace std;

const double BILLION = 1E9;

 /* Print ALL pairs of number from the given array a[0...a_len-1] that adds up to K 
    @param intList: the list of int values 
    @param K: the sum we want to make
   */
void PairsAddupToK (int a[], int a_len,  int K)
{
 //TODO by you
}
   
/* Print ALL triples of numbers from the given array a[0...a_len-1] that adds up to K 
@param intList: the list of int values 
@param K: the sum we want to make
*/
void TriplesAddupToK (int a[], int a_len, int K)
{
        //todo by you
}
   
/* Print ALL subsets of numbers from the given array, a[0...a_len-1 that adds up to K 
this function solves the problem iteratively 
NOTE: WE assume a_len<32 (so that we can use int (which uses 32 or 64 bits) 
  as code to decide subset  
@param intList: the list of int values 
@param K: the sum we want to make
*/
void SubsetsAddupToK (int a[], int a_len, int K)
{
        //todo by you
}

            
        
//Recursive solution to SubsetAddupToK 
/* This functions tries to use numbers from a[left...right] to make sum 
 @param a[] array of int
 @n: a[left...right] is the list of numbers to use
 @currentSum: current sum we have made using numbers in numsUsed
 @finalSum: final sum that we need to make
 @numsUsed: numbers that are used to get us here */
bool SubsetsAddupToK (int  a[], int left, int right, int currentSum, int finalSum, vector<int> numsUsed)
{
        //Three base cases: 
        //case 1: what remains to make is negative: we have overshot... 
        if (currentSum>finalSum)
                return false; 

        //case 2: we made it! 
        // Result is only displayed at the base case. 
        if (currentSum==finalSum)
        {
                cout <<"Solution:";
                for (int i=0;i<numsUsed.size();i++)
                        cout <<numsUsed[i]<<",";
                cout <<endl;
                return true;
        }

        //case 3: we don't have any number to use: fails. 
        if (left>right && currentSum < finalSum)
                return false;


        //General calse: what remains to make is positive, and we have numbers to use 
        bool res1=false, res2=false;

        // Explore both possibilities: Use a[left] or not 
        //  1) include a[left] in the sum, i.e., make sum-a[left] using a[left+1...right]  
        vector<int> newNums = numsUsed;
        newNums.push_back (a[left]); //now a[left] is used ... 

        res1 = SubsetsAddupToK(a, left+1, right, currentSum+a[left], finalSum,newNums);
            // here the currentSum is increased by a[left], a[left] is added into list of 
            // numbers used... 

        //  2) do not include a[left] in the sum, i.e., make sum using a[left+1...right]  
        //     currentSum, finalSum, numsUsed is not changed 
        res2 = SubsetsAddupToK (a, left+1, right, currentSum, finalSum, numsUsed);
                                    //^+1 so that a[left] is not considered any more

        //if either of the above two succeeded, return true 
        if (res1 || res2)
                return true;
        else
                return false;
}


/* Compare the running time of three functions for input size n 
 @param n: the length of vecotr/list
 */ 
void  MeasureRunningTime (int a[], int a_len)
{
        struct timespec start, finish;
        double r1, r2, r3, r4;


           clock_gettime (CLOCK_REALTIME, &start);
           PairsAddupToK (a, a_len, 100);
           clock_gettime (CLOCK_REALTIME, &finish);
           r1 = (finish.tv_sec - start.tv_sec)+
                        (finish.tv_nsec-start.tv_nsec)/BILLION;


           clock_gettime (CLOCK_REALTIME, &start);
           TriplesAddupToK (a, a_len, 100);
           clock_gettime (CLOCK_REALTIME, &finish);
           r2 = (finish.tv_sec - start.tv_sec)+
                        (finish.tv_nsec-start.tv_nsec)/BILLION;

           clock_gettime (CLOCK_REALTIME, &start);
           SubsetsAddupToK (a, a_len, 100); 
           clock_gettime (CLOCK_REALTIME, &finish);
           r3 = (finish.tv_sec - start.tv_sec)+
                        (finish.tv_nsec-start.tv_nsec)/BILLION;

           clock_gettime (CLOCK_REALTIME, &start);
           vector<int> results;
           SubsetsAddupToK (a, 0, a_len, 0, 100, results); 
                                        //^ current sum=0, final sum=100
           clock_gettime (CLOCK_REALTIME, &finish);
           r4 = (finish.tv_sec - start.tv_sec)+
                        (finish.tv_nsec-start.tv_nsec)/BILLION;

           cout <<"n="<<a_len<<"\t";
           cout <<"Pairs"<<"\t"<< r1<<"s\t";
           cout <<"Triples"<<"\t"<< r2<<"s\t";
           cout <<"Subsets"<<"\t"<< r3<<"s\t";
           cout <<"SubsetsR"<<"\t"<< r4 <<"s\t"<<endl;
}

int main()
{
        vector<int> numsUsed; //this is empty initially 

        int a5[5] = {50,90,20,30,10};
        int a10[10] = {50, 33, 90, 2, 20, 
                72, 30,10, 92, 8};
        int a20[20] = {50, 33, 11, 79, 90,
                2, 20, 72, 30,10, 
                92, 8, 99, 101, 25,
                71, 48, 72, 35, 9};
        int a30[30] = {50, 33, 11, 79, 90, 
                2, 20, 72, 30,10, 
                92, 8, 99, 101, 25, 
                71, 48, 72, 35, 9,
                37, 41, 55, 73, 67,
                66, 22, 11, 6, 4};

        //Testing 
        //Display all different ways to make 100 using a5[0...4]
        int SumToMake = 100;
        int curSum=0; 
        SubsetsAddupToK (a5, 0, 4, curSum, SumToMake, numsUsed);

        /* Measuring and comparing running time  
        MeasureRunningTime (a5, 5);
        MeasureRunningTime (a10, 10);
        MeasureRunningTime (a20, 20); */
        MeasureRunningTime (a30, 30);
}

Answer 1

P.S : Please go through with the solution attentively, I don't need thumbsup , but don't dislike it before checking it carefully.

#include <iostream>
#include <bitset>
#include <vector>
#include <time.h>
#include <math.h>
using namespace std;

const double BILLION = 1E9;

void PairsAddupToK (int a[], int a_len, int K)
{
   for (int i = 0; i < a_len; i++)
for (int j = i + 1; j < a_len; j++)
if (a[i] + a[j] == K)
cout << "(" << a[i] << ", "
<< a[j] << ")" << endl;

}

/* Print ALL triples of numbers from the given array a[0...a_len-1] that adds up to K
@param intList: the list of int values
@param K: the sum we want to make
*/
void TriplesAddupToK (int a[], int a_len, int K)
{
int l, r;
for (int i = 0; i < a_len - 2; i++)
   {
       cout<<"\n";
for (int j = i + 1; j < a_len - 1; j++)
       {
for (int k = j + 1; k < a_len; k++)
           {
if (a[i] + a[j] + a[k] == K)
               {
cout << "Triplet is " << a[i] << ", " << a[j] << ", " << a[k];   
}
}
}
}
}

/* Print ALL subsets of numbers from the given array, a[0...a_len-1 that adds up to K
this function solves the problem iteratively
NOTE: WE assume a_len<32 (so that we can use int (which uses 32 or 64 bits)
as code to decide subset
@param intList: the list of int values
@param K: the sum we want to make
*/
void sumSubsets(int set[], int n, int target,int size)
{
// Create the new array with size
// equal to array set[] to create
// binary array as per n(decimal number)
int x[size];
int j = size - 1;
  
// Convert the array into binary array
while (n > 0)
{
x[j] = n % 2;
n = n / 2;
j--;
}
  
int sum = 0;
  
// Calculate the sum of this subset
for (int i = 0; i <size; i++)
if (x[i] == 1)
sum = sum + set[i];
  
// Check whether sum is equal to target
// if it is equal, then print the subset
if (sum == target)
{
cout<<("{");
for (int i = 0; i < size; i++)
if (x[i] == 1)
cout << set[i] << ", ";
cout << ("}, ");
}
}
void SubsetsAddupToK (int a[], int a_len, int K)
{
int x = pow(2, a_len);
  
// Run loop till total no. of subsets
// and call the function for each subset
for (int i = 1; i < x; i++)
sumSubsets(a, i, K,a_len);
}

  
  
//Recursive solution to SubsetAddupToK
/* This functions tries to use numbers from a[left...right] to make sum
@param a[] array of int
@n: a[left...right] is the list of numbers to use
@currentSum: current sum we have made using numbers in numsUsed
@finalSum: final sum that we need to make
@numsUsed: numbers that are used to get us here */
bool SubsetsAddupToK (int a[], int left, int right, int currentSum, int finalSum, vector<int> numsUsed)
{
//Three base cases:
//case 1: what remains to make is negative: we have overshot...
if (currentSum>finalSum)
return false;

//case 2: we made it!
// Result is only displayed at the base case.
if (currentSum==finalSum)
{
cout <<"Solution:";
for (int i=0;i<numsUsed.size();i++)
cout <<numsUsed[i]<<",";
cout <<endl;
return true;
}

//case 3: we don't have any number to use: fails.
if (left>right && currentSum < finalSum)
return false;

//General calse: what remains to make is positive, and we have numbers to use
bool res1=false, res2=false;

// Explore both possibilities: Use a[left] or not
// 1) include a[left] in the sum, i.e., make sum-a[left] using a[left+1...right]
vector<int> newNums = numsUsed;
newNums.push_back (a[left]); //now a[left] is used ...

res1 = SubsetsAddupToK(a, left+1, right, currentSum+a[left], finalSum,newNums);
// here the currentSum is increased by a[left], a[left] is added into list of
// numbers used...

// 2) do not include a[left] in the sum, i.e., make sum using a[left+1...right]
// currentSum, finalSum, numsUsed is not changed
res2 = SubsetsAddupToK (a, left+1, right, currentSum, finalSum, numsUsed);
//^+1 so that a[left] is not considered any more

//if either of the above two succeeded, return true
if (res1 || res2)
return true;
else
return false;
}

/* Compare the running time of three functions for input size n
@param n: the length of vecotr/list
*/
void MeasureRunningTime (int a[], int a_len)
{
struct timespec start, finish;
double r1, r2, r3, r4;

clock_gettime (CLOCK_REALTIME, &start);
PairsAddupToK (a, a_len, 100);
clock_gettime (CLOCK_REALTIME, &finish);
r1 = (finish.tv_sec - start.tv_sec)+
(finish.tv_nsec-start.tv_nsec)/BILLION;

clock_gettime (CLOCK_REALTIME, &start);
TriplesAddupToK (a, a_len, 100);
clock_gettime (CLOCK_REALTIME, &finish);
r2 = (finish.tv_sec - start.tv_sec)+
(finish.tv_nsec-start.tv_nsec)/BILLION;

clock_gettime (CLOCK_REALTIME, &start);
SubsetsAddupToK (a, a_len, 100);
clock_gettime (CLOCK_REALTIME, &finish);
r3 = (finish.tv_sec - start.tv_sec)+
(finish.tv_nsec-start.tv_nsec)/BILLION;

clock_gettime (CLOCK_REALTIME, &start);
vector<int> results;
SubsetsAddupToK (a, 0, a_len, 0, 100, results);
//^ current sum=0, final sum=100
clock_gettime (CLOCK_REALTIME, &finish);
r4 = (finish.tv_sec - start.tv_sec)+
(finish.tv_nsec-start.tv_nsec)/BILLION;

cout <<"n="<<a_len<<"\t";
cout <<"Pairs"<<"\t"<< r1<<"s\t";
cout <<"Triples"<<"\t"<< r2<<"s\t";
cout <<"Subsets"<<"\t"<< r3<<"s\t";
cout <<"SubsetsR"<<"\t"<< r4 <<"s\t"<<endl;
}

int main()
{
vector<int> numsUsed; //this is empty initially

int a5[5] = {50,90,20,30,10};
int a10[10] = {50, 33, 90, 2, 20,
72, 30,10, 92, 8};
int a20[20] = {50, 33, 11, 79, 90,
2, 20, 72, 30,10,
92, 8, 99, 101, 25,
71, 48, 72, 35, 9};
int a30[30] = {50, 33, 11, 79, 90,
2, 20, 72, 30,10,
92, 8, 99, 101, 25,
71, 48, 72, 35, 9,
37, 41, 55, 73, 67,
66, 22, 11, 6, 4};

//Testing
//Display all different ways to make 100 using a5[0...4]
int SumToMake = 100;
int curSum=0;
SubsetsAddupToK (a5, 0, 4, curSum, SumToMake, numsUsed);

/* Measuring and comparing running time
MeasureRunningTime (a5, 5);
MeasureRunningTime (a10, 10);
MeasureRunningTime (a20, 20); */
MeasureRunningTime (a30, 30);
}