Moule Lin
← All notes

Recursive Backtracking

RecursionBacktrackingC++

With multiple levels of recursion, the human brain cannot simulate the recursive process, so you need a recursion tree

#include <iostream>
#include <vector>
using namespace std;
void recursion(vector<int>& nums,vector<int>& temp,int target, int sum,int count,int& len,int current){
    //The three steps of recursion
    //- Determine the parameters and return value
    //- Determine the termination condition
    //- Write the logic for a single level of recursion
    
    if(sum>=target){
        //This is only reached during recursion
        len = min(len, count);
        return;
    }
    for(int i=current;i<nums.size();i++){
        //Originally 4: first backtrack to 4, and the for loop ends
        //Start the second backtrack, i=3 (at this point sum, count and temp have all removed the i=3 and i=4 cases); after the for, i=4
        // Then sum adds the i=4 case, skipping i=3
        //Then backtrack to i=2; after the for, i=3 (here two levels of recursion stack up again (i=3 and i=4),
        //and for i=3 the value of i=2 is gone because it was backtracked; i=4 is a child node of i=3)
        //Use the recursion tree to analyse the whole recursive process
        count++;
        sum += nums[i];
        temp.push_back(nums[i]);
        recursion(nums, temp,target,sum,count,len,i+1);
        //Backtracking starts here: sum, count and temp are all rolled back, but note that i is not
        sum -= nums[i];
        temp.pop_back();
        count--;    
    }
}
int minSubArrayLen(int s, vector<int>& nums) {  
    int len=999;
    vector<int> temp;
    recursion(nums,temp,s,0,0,len,0);
    if (len==999)
        return 0;
    return len;
}
int main(int argc, const char * argv[]) {
    // insert code here...
    vector<int> nums={1,2,3,4,5};
    int len = minSubArrayLen(15,nums);
    cout << len<<endl;
    return 0;
}

All of the following can be solved with recursive backtracking

When you meet these problems, remember to draw the recursion tree first