CODEWITHSUNDEEP
c++crecursionsubset
user9762426
user9762426

Reputation:

Finding the maximum sum from the subset sum using recursion

I want to print only the maximum sum from the subset sum. What I want actually is to compare all the subset sum values in the function and then return only the maximum sum in the main function.

What I tried to do was to save the subset sum values in a new array. Then compare the values in there. But I couldn't manage to do that as it returns nothing. I want suppose input array size is n = 5, number of elements to sum is r = 3 And array is :

{1,2,3,4,5}

Then maximum sum should be 3 + 4 + 5 = 12. But my code returns all the sum.

I want to save the sum values in the newArray

newArray[] = sum;

then find the maximum values from the newArray.

This is my code :

#include <stdio.h>
#include <iostream>
using namespace std;

void combinationRecursion(int start, int end, int index, int r, int *arr, int *data, int sum){

if(r == index){
    for(int i=0; i<r; i++){
        int val = data[i];
        cout<<val<<' ';
        sum = sum + data[i];

    }
    printf("sum %d\n",sum);
    printf("\n");

}
for(int i=start; i<end; i++){
    data[index] = arr[i];
    combinationRecursion(i+1, end, index+1, r, arr, data, sum);
   }
 }

 int main() {
     int arr[100], n, data[100], r;
     scanf("%d%d",&n,&r);

for(int i=0; i<n; i++) {
    scanf("%d",&arr[i]);
}
combinationRecursion(0, n, 0, r, arr, data, 0);
}

Upvotes: 1

Views: 856

Answers (3)

user9762426
user9762426

Reputation:

finally I've been able to solve this by setting max globally. this's the modified version

int max1 = 0;
int combinationRecursion(int start, int end, int index, int r, int *arr, int *data){

if(r == index){
        int sum = 0;
    for(int i=0; i<r; i++){
        int val = data[i];
        sum = sum + data[i];
    }
     if(max1<sum){
        max1 = sum;
   }

}
for(int i=start; i<end; i++){
    data[index] = arr[i];
    combinationRecursion(i+1, end, index+1, r, arr, data);
}
 return max1;
}

Upvotes: 1

Surt
Surt

Reputation: 16099

Let see if we can do it using std::algorithms (untested code).

std::partial_sum(data.begin(), data.end(), std::plus<int>);
std::vector<int> subSetSum;
subSetSum.reserve(data.size()); // -3 but meh.
std::transform(data.begin(), data.begin()+subSetLength-1, std::back_inserter(subSetSum), std::minus<int>); // will be negative
auto maxSum = -std::min_element(subSetSum.begin(), subSetSum.end());

But there is no recursion here ...

Upvotes: 0

NiVeR
NiVeR

Reputation: 9786

If you are interested in the subset of size k out of set with cardinality n then you don't need to do any of the combination generation stuff. You can just sort the array in decreasing order and pick the top k elements, as they are sorted in decreasing order they will give the maximum sum of subset of size k.

Upvotes: 2

Related Questions