hi, i’m trying to find the max sum from the subset sum. But i have only found out the subset sum not the max subset sum from there. 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 it returns all combination sum. This is my code
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++){
sum = sum + data[i];
}
printf("sum %d\n",sum);
printf("\n");
return;
}
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);
}
This is my code . Can somebody tell me what change should i give here to find only the max sum value.
I’ve edited your post for readability. When you enter a code block into the forum, precede it with a line of three backticks and follow it with a line of three backticks to make easier to read. See this post to find the backtick on your keyboard. The “preformatted text” tool in the editor (</>) will also add backticks around text.
1 Like
Can you post the problem statement? Just asking incase of a misunderstanding somewhere
Does this have to be done with recursion, or can this be done iteratively?
it’ll be helpful if it is done with the recursion. Suppose if we give input array = {2,3,4} and take only 2 combination each time then the sums are 5, 6 and 7. My code return all the values . But I want only the max value 7
Right, I wasn’t sure if it was a subset sum (as in values in a row) you were looking for, or the maximum possible sum of an arbitrary combination of a number of variables
It’s worth noting that if you have an array of all possible sums then all you need to do is find the maximum within that array, which is the easiest way to solve this
I can’t really say that that recursive method is particularly great for this problem though, it’s definitely not very readable, but we can discuss another way after you’ve done that and submitted it I guess?
Edit to make myself more clear: You can keep track of each one found instead of just printfing it, that’s what I was meaning
this is the main problem. As I haven’t been able to save the sum values in an array. Do you have any idea how i can save those sum values in an array ?
You have the sum each time at this line:
printf("sum %d\n", sum);`
But you only printf it each time. Instead of just printing it, you could store it in another array (with another pointer argument)
Or even better to save a bit of space, you could store just the maximum sum found so far in another pointer argument:
*max = *max < sum ? sum : *max;
To be honest though I really wouldn’t be diving for a void recursive function for this, but each to their own
when i tried to save the sum values in an array how can I increment the index? As the index is always one for recursive function. It only increments 1 time as, recursively when the condition r==index fulfills k is initialize to 0 again. So i cant track of index 1, 2 ,3
int max[100], k = 0;
if(r == index){
for(int i=0; i<r; i++){
sum = sum + data[i];
}
// printf("sum %d\n",sum);
max[k] = sum;
k++;
printf("k i %d ",k);
return;
}
It’s C so you’d have to keep track of the index yourself too 
you’d save a lot of space by just keeping track of the max found so far, there’s nCr combinations so you’d need that large an array
use push to push the new values at the end of the array instead
It seems as though recursion is probably still new and unfamiliar for you. I would suggest first solving this task imperatively. If you want to solve this recursively, take the time to work out your logic flow with a pen and paper and then redesign your function accordingly.
yah recursion is quite difficult for me. I had to use recursion here because I couldn’t solve the combination problem iteratively. I’ll try this again
I’ve finally solved it by setting max value globally. Now it works.
int max1 = 0;
if(max1<sum){
max1 = sum;
return max1;