Why TLE in the no repeated combination problem


  • 0
    R
    const int MAXNUM=100000;
    vector<vector<int> > allsets;
    
    class Solution {
    public:
        bool select[MAXNUM];
    void SubsetsSum(vector<int> num, int from, int to, int sum)
    {
    	if(from>to)//all traverse
    	{
    		if(sum==0)
    		{
    			vector<int> oneset;
    			for(int i=0;i<=to;i++)
    			{
    				if(select[i])
    					oneset.push_back(num[i]);
    			}
    			if(oneset.size()>0)
    				allsets.push_back(oneset);
    		}
    	}
    	else//from<=to
    	{
    		/*
    		if(sum==0)
    		{
    			vector<int> oneset;
    			for(int i=0;i<=from-1;i++)
    			{
    				if(select[i])
    					oneset.push_back(num[i]);
    			}
    			if(oneset.size()>0)
    				allsets.push_back(oneset);
    		}*/
    		if(sum>=0)
    		{
    			select[from]=false;
    			if(!IsRepeatedCombination(num,from))
    				SubsetsSum(num,from+1,to,sum);
    			select[from]=true;
    			if(!IsRepeatedCombination(num,from))
    				SubsetsSum(num,from+1,to,sum-num[from]);
    		}
    		else
    			;
    	}
    }
    bool IsRepeatedCombination(vector<int> num, int enddup)
    {
    	if(enddup==2)
    		int x=1;
    	if( (enddup<=num.size()-2 && num[enddup]!=num[enddup+1]) || enddup==num.size()-1)//last duplicate element
    	{
    		int i=enddup;
    		while(i>=1 && num[i-1]==num[enddup])
    			i--;
    		int startdup=i;
    
    		i=enddup;
    		while(i>=startdup && select[i]==true)
    			i--;
    		while(i>=startdup && select[i]==false)
    			i--;
    		if(i==startdup-1)
    			return false;
    		else
    			return true;
    	}
    	else
    		return false;
    }
    
    vector<vector<int> > combinationSum2(vector<int> &num, int target)
    {
    	sort(num.begin(),num.end());
    	memset(select,0,num.size()*sizeof(bool));
    	allsets.clear();
    	SubsetsSum(num,0,num.size()-1,target);
    	return allsets;
    }
    };
    

    I think may be my solution is right, but how to reduce time, if I prone it, it will get repeated answers.
    I have a bool function to check if this continous repeated elements have occured before, that is only 0000, 0001,0011,0111,1111 would be not repeated as they first occured and other would not recursive later. These are select[], for continous elements.


  • 0
    R

    I have ac, exists a dp algorithm, that is more efficient, so dfs would tle,,,,,


Log in to reply
 

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