Someone help me please,i'm confused by my C++ answer,what's wrong with it?


  • 0
    B

    when it comes to case 171, my C++ solution has a wrong output.
    Input:[4,4,2,1,4,2,2,1,3]
    6
    Output:[[1,1,2,2],[1,1,4],[1,2,3],[1,5],[2,2,2],[2,4]]
    Expected:[[1,1,2,2],[1,1,4],[1,2,3],[2,2,2],[2,4]]
    i don't know the reason.This case is the only one that my solution doesn't pass.I used backtracking to solve the problem.Here is my code.

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(),candidates.end());
        vector<vector<int>> r;
        vector<int>temp;
        int l=0;
        int pop=INT_MAX;
        int n=target;
        backrtracking(r,temp,candidates,target,l,n,pop);
        return r;
    }
    
    
    void backtracking(vector<{vector<int>>&result,vector<int>&temp,vector<int>candidates,int ret,int k,int n,int pop){
    if (ret == 0)
    {
    	result.push_back(temp);
    }
    else
    {
    	for (int i = k; i<candidates.size(); i++)
    	{
    	     while(candidates[i]==pop)
    	    i++;
    	    while(i>0&&candidates[i]==candidates[i-1]&&ret==n)
    	    i++;
    		ret = ret - candidates[i];
    		if (ret<0)
    			break;
    		temp.push_back(candidates[i]);
    		k = i+1;
    		backrtracking(result, temp, candidates, ret,k,n,pop);
    		ret = ret + temp.back();
    		pop=temp.back();
    		temp.pop_back();
    	}
    }}

Log in to reply
 

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