Variable in a recursive function doesn't update itself C-CodePudding

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);
}

CodePudding user response：

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).