Share my simple solution : only using 24ms and without using set to handle duplicates


  • 1
    Z
    class Solution {
    public:
    	vector<vector<int>> res;
    	void go(int startpos, vector<int>oneres, vector<int> &num, int target)
    	{
    		for (int i = startpos; i < num.size(); i++)
    		{
    			if(num[i]<target)
    			{
    				oneres.push_back(num[i]);
                    // In question"Combination Sum", here should be i instead of i+1, cuz it allow
                    // using one number more than once
    				go(i + 1, oneres, num, target-num[i]);
    				oneres.pop_back();
    			}
    			else if(num[i]==target)
    			{
    				oneres.push_back(num[i]);
    				res.push_back(oneres);
    				oneres.pop_back();
    				return;
    			}
    			else
    			{
    				return;
    			}
    			// handle duplicates
    			while (i < num.size() - 1 && num[i] == num[i + 1])
    				i++;
    		}
    	}
    	vector<vector<int> > combinationSum2(vector<int> &num, int target) {
    		sort(num.begin(), num.end());
    		vector<int>oneres;
    		go(0, oneres, num, target);
    		return res;
    	}
    };

  • 0
    H

    Why keep showing: Please provide more information - at least 30 characters
    I wrote more than 30 OK?

    I think num[i]<target/2 is enough since elements after num[i] will greater target/2 which will definitely exceed the target in the next recursion.

    I use a variable to store the last number, which used to handle duplication. However your method share the same thought but less comparisons than mine.

    Good Job!

    Here's my AC python solution:

    class Solution:
        # @param candidates, a list of integers
        # @param target, integer
        # @return a list of lists of integers
        def combinationSum2(self, candidates, target):
            def combinationSum(candidates,target,combination,ret):
            	length = len(candidates)
            	if length == 0 or candidates[0]>target:
            		return
            	last = None
            	for i in range(length):
            		if candidates[i] <= target/2 and candidates[i] != last:
            			combinationSum(candidates[i+1:],target-candidates[i],combination+[candidates[i]],ret)
            		elif candidates[i]  == target and candidates[i] != last:
            			ret.append(combination+[candidates[i]])
            		else:
            			continue
            		last = candidates[i]
    
           	ret = []
            combinationSum(sorted(candidates),target,[],ret)
            return ret

  • 0
    H

    Please ignore "Please provide more information - at least 30 characters". That's stupid


  • 0
    T

    If I'm not mistaken the duplication avoidance will cause a problem for the following input

    [2,2,2,3], 5


Log in to reply
 

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