Variable in a recursive function doesn't update itself C++

Question

Im trying to solve a leetcode problem called Partition Equal Subset Sum So basically we are given an array of some integers an we need to find out if we can create a subset of equal sum based on the array, for example [1, 5, 11, 5] can be divided into equal sum with [1,5,5] and [11] since the sum of both are equal.

I tried using recursion to solve this problem but the problem is that the boolean variable hasil doesn't update itself when given a new value. It just returns the value that I gave it in the declaration, so for example if I declare hasil = true, then the return value will always be true.

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
bool solve(vector<int>& nums, int sum1, int sum2, int index){
    bool hasil = false;
    if(index != nums.size() ){
        solve(nums,sum1+nums[index],sum2,index + 1);
        solve(nums,sum1,sum2+nums[index],index + 1);
    }

    if(sum1 == sum2 && index == nums.size() ){
        //cout << sum1 << " " << sum2 << endl;
        hasil = true;
        //return hasil;
    } else if(sum1 != sum2 && index == nums.size() ){
        //cout << sum1 << " " << sum2 << endl;
        hasil = false;
        //return hasil;
    }

    return hasil;
    //hasil will always return as in declaration, in this case it's false
}

int main()
{
    vector<int> nums{ 1,5,11,5 };
    int sum1 = 0;
    int sum2 = 0;
    int index = 0;
    return solve(nums,sum1,sum2,index);
}

You completely ignore the results of the recursive function calls. And `hasil` is a local variable to each function invocation, they are not shared between them — UnholySheep, Jan 30 '23 at 10:50
Each call has its own `hasil`. Rather than just calling a nested `solve(...)`, you must do `if (solve(...)) hasil = ...`. — HolyBlackCat, Jan 30 '23 at 10:50
calling a recursive function is like calling a non-recursive function. What do you expect to happen when you call `solve` and why? — 463035818_is_not_an_ai, Jan 30 '23 at 10:55
The first three lines are exceedingly bad code. Don't learn C++ with these competitive coding sites. Try [some books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list/388282#388282) instead. — Passer By, Jan 30 '23 at 10:59
[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — Jason, Jan 30 '23 at 11:05
Unrelated: [Why should I **not** `#include `?](https://stackoverflow.com/Questions/31816095/Why-Should-I-Not-Include-Bits-Stdc-H.) and please don't do `#define ll long long` `#define pb push_back` - it's only confusing — Ted Lyngmo, Jan 30 '23 at 11:20

john · Answer 1 · 2023-01-30T11:14:09.940

It seems that beginners get very confused about returning values from recursive functions. But the rules for returning values from recursive functions are exactly the same as the rules for non-recursive functions.

The code I think you are trying to write is this

bool solve(vector<int>& nums, int sum1, int sum2, int index) {
    if (index < nums.size()) {
        return solve(nums,sum1+nums[index],sum2,index + 1) ||
           solve(nums,sum1,sum2+nums[index],index + 1);
    }
    else {
        return sum1 == sum2;
    }
}

Notice that unlike your version I don't ignore the return value from the recursive calls to solve. Instead of expecting some kind of magical update to happen I capture the return value and use it to calculate a new return value, i.e. solve(...) || solve(...), in other words if either recursive call returns true then this call will also return true.

Note the (hopefully) correct version is much simpler, and doesn't even need the variable you were trying to update (thanks @user20716902).

I beleive `solve` can be simplified further, the final `else if` is not required, as `hasil` is already `false`. — user20716902, Jan 30 '23 at 11:13

Variable in a recursive function doesn't update itself C++

1 Answers1