How can I use a variable from a previous recursive call?-CodePudding

The general problem: Given an array of integers nums and an integer k. A continuous subarray is called nice if there are k odd numbers on it. Return the number of nice sub-arrays.

My question: I want to solve this problem recursively. The part I'm struggling to implement is how do I use the count from every previous recursive call and sum up all the counts, and return one last count like it is shown in the attempt.

Example:

Input: nums = [1,1,2,1,1], k = 3
Output: 2
Explanation: The only sub-arrays with 3 odd numbers are [1,1,2,1] and [1,2,1,1].

My attempt:

int helperFunction(vector<int> &nums, int k, int starter, int count)
{
    int sum=0;
    if (starter >= nums.size())
    {
        return count;
    }
    for (int i = starter; i < nums.size(); i  )
    {
        if (nums[i] % 2 == 1)
        {
            if (  sum == k)
            {
                count  = nums.size() - i;
                sum = 0;
            }
        }
    }
    return helperFunction(nums, k, starter   1, count);
}
int numberOfSubarrays(vector<int> &nums, int k)
{
    return helperFunction(nums, k, 0, 0);
}

int main()
{
    vector<int> mine;
    int myints[] = {1, 1, 2, 1, 1};

    mine.assign(myints, myints   5);
    cout << "Output : " << numberOfSubarrays(mine, 3);
    return 0;
}

Return Value:

The return value of this actual attempt is 0 means the program is at least not wrong syntactically.

CodePudding user response：

it's not particularly good candidate for recursion. might be possible to solve with just one pass on the array.

That said, small adjustments to your code could make it work. There is no reason to pass count into the recursive method.

Your method calculates the number of subarrays that are 'nice' starting with the given index. Add that to the number that start at the next index and return it.

int helperFunction(vector<int> &nums, int k, int starter)
{
    int sum=0, count=0;
    if (starter >= nums.size())
    {
        return 0;
    }
    for (int i = starter; i < nums.size() && sum <= k; i  )
    {
        if (nums[i] % 2 == 1)
        {
            sum  ;
        }
        if (sum == k)
        {
            count  ;
        }        
    }
    return helperFunction(nums, k, starter   1)   count;
}

I'm not sure your counting was correct. This could be optimized a lot, but this should demostrate the recursive approach.