Why my code for "Combination Sum" cannot be accepted?


  • 0
    F

    This is my code:

    class Solution {
    public:
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
    	vector<vector<int> > result;
    	if (candidates.empty()) {
    		return result;
    	}
    
    	vector<int> elements;
    
    	int i = candidates.size() - 1;
    	while (candidates[i] > target && i >= 0) {
    		--i;
    	}
    	if (i == -1) {
    		return result;
    	}
    
    	findCombinationSum(candidates, i, target, elements, result);
    	return result;
    }
    
    void findCombinationSum(vector<int>& candidates, int current, int target, vector<int> &elements, vector<vector<int> > &result) {
    	if (target < 0 || current < 0) {
    		return;
    	}
    
    	int elem = candidates[current];
    
    	for (int i = elem; i <= target; i += elem) {
    		elements.push_back(elem);
    		if (target - i == 0) {
    			result.push_back(elements);
    			break;
    		}
    		findCombinationSum(candidates, current - 1, target - i, elements, result);
    	}
    	for (size_t i = 0; i < target / elem; i++)
    	{
    		elements.pop_back();
    	}
    	findCombinationSum(candidates, current - 1, target, elements, result);
    }
    };
    

    This is the wrong answer message:

    Input: [1,2], 3
    Output: [[2,1],[1,1,1]]
    Expected: [[1,1,1],[1,2]]

    Yes, I can sort each vector, but how can I reorder the vector of vector.

    I think my answer should be accept, right?


  • 0
    M

    In the problem description, it requires:

    Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
    

    While you have the correct values, if you completely ignore one of the guidelines of a project, the solution might not be any good for its purpose.

    I am pretty sure that the order of the vectors inside the solution vector do not matter, just the order of the elements in those vectors. Just correct the order of those elements and it should pass, assuming nothing else is wrong.


Log in to reply
 

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