A little confusion in backtracking problems.
Parvindar Singh
71

Let's see the problem Combination Sum.
I usually write code this way.
(that while loop is there because we can reuse the same element to make the given target)

    vector<vector<int>> res;
    
    void util(vector<int>& candidates,vector<int> ans,int target,int i)
    {
        if(target == 0)
        {
            res.push_back(ans);
            return;
        }
        if(i == candidates.size())
            return;
        
        util(candidates,ans,target,i+1);
        while(target - candidates[i]>=0)
        {
            ans.push_back(candidates[i]);
            target-=candidates[i];
            util(candidates,ans,target,i+1);
        }
    }

whereas I have seen most of the people write code this way - (with a for loop)

    void backtrack( vector<vector<int>> &result,vector<int>& candidates,
                   vector<int> &curr, int start, int need ) {
        if( 0 == need ) {
            result.push_back( curr );
        }
        for( int i=start; i < candidates.size() && need >= candidates[i]; i++ ) {
            curr.push_back( candidates[i] );
            // not i + 1 because we can reuse same elements
            backtrack( result, candidates, curr, i, need - candidates[i] ); 
            curr.pop_back();
        }
    }

Can someone explain if there is any efficiency difference in both cases.?
Which one is more optimized?
is there a difference in recursive stack space complexity?

Comments (0)