16ms c++, very simple and easy to understand backtracking


  • 0
    I

    very simple and easy to understand backtracking

    void combinationSumHelper(vector<int>& a, vector<int>& sol, vector<vector<int>>& rtn,  int key, int index)
    {
    	if (key == 0) rtn.push_back(sol);
    	if (index < a.size() - 1 && a[index] == a[index + 1]) index++;
    	for (int i = index; i < a.size() && key - a[i] >= 0; i++)
    	{
    		sol.push_back(a[i]);
    		combinationSumHelper(a, sol, rtn, key - a[i], i);
    		sol.pop_back(); 
    	}
    }
    
    vector<vector<int>> combinationSum(vector<int>& a, int key)
    {
    	sort(a.begin(), a.end());
    	vector<vector<int>> rtn;
    	vector<int> sol;
    	combinationSumHelper(a, sol, rtn, key, 0);
    	return rtn;
    }
    

  • 0
    Y

    Can I ask why we need "sol.pop_back(); " ? I couldn't figure it out. We should first push a[i] to the end of sol, then continue to do combinationSumHelper(a, sol, rtn, key - a[i], i);, why do we need to do sol.pop_back() later? What got popped out?


  • 0
    I

    you are basically simulating how a stack works. when you enter a function you push all variables into the stack and when you leave a fucntion you pop all associated variables out of the stack.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.