Cannot pass the case [4, 3, 10], 10 (Combination Sum)


  • 0
    M

    Dear all:

    I have passed 167/168 of the test cases and was stuck with the last one [4, 3, 10], 10

    The shown error message is as below:

    Input: [4,3,10], 10

    Output: [[3,3,4],[10],[10]]

    Expected: [[3,3,4],[10]]

    Strange enough, on my local computer with compiler information (g++ follow the C++11 ISO C++ language standard [-std=c++11]), the result is [[3,3,4],[10]] instead of that indicated by leetCode, [[3,3,4],[10],[10]]

    In short there is a subtle discrepency between my working platform and the leetCode platform.

    Even more, I believe I have ever passed the test case [2, 3, 6, 7], 7 on leetCode platform, and I think it is essentially the same as [4, 3, 10], 10

    Very puzzled and would really apprciate if someone can answer this tricky question.

    Below is my code (based on recursion):

    vector<vector<int>> combinationSum(vector<int> &candidates, int target)
    {
        vector<vector<int>> combs;
        vector<int> comb;
    
        if (candidates.empty())
            return combs;
        else {
            sort(candidates.begin(), candidates.end());
            vector<int>::iterator it_head = candidates.begin();
            while ((*it_head <= target)) {
                if ((*it_head <= target/2)||(*it_head == target))
                    combSum(combs, comb, candidates, it_head, target);
                it_head++;
            }
        }
        return combs;
    }
    
    void combSum(vector<vector<int>> &combs, vector<int> comb, vector<int> &candidates, vector<int>::iterator it_head, int target)
    {
        if (*it_head == target) {
            comb.push_back(*it_head);
            combs.push_back(comb);
        }
        else if  (*it_head > target)
            comb.clear();
        else {
            comb.push_back(*it_head);
            for (vector<int>::iterator jt_head = it_head; jt_head < candidates.end(); jt_head++)
                combSum(combs, comb, candidates, jt_head, target-*it_head);
        }
    }

  • 1
    D

    I just copied your code and pasted in OJ and it passed.

    class Solution {
    public:
        vector<vector<int>> combinationSum(vector<int> &candidates, int target)
        {
            vector<vector<int>> combs;
            vector<int> comb;
        
            if (candidates.empty())
                return combs;
            else {
                sort(candidates.begin(), candidates.end());
                vector<int>::iterator it_head = candidates.begin();
                while ((*it_head <= target)) {
                    if ((*it_head <= target/2)||(*it_head == target))
                        combSum(combs, comb, candidates, it_head, target);
                    it_head++;
                }
            }
            return combs;
        }
    
        void combSum(vector<vector<int>> &combs, vector<int> comb, vector<int> &candidates, vector<int>::iterator it_head, int target)
        {
            if (*it_head == target) {
                comb.push_back(*it_head);
                combs.push_back(comb);
            }
            else if  (*it_head > target)
                comb.clear();
            else {
                comb.push_back(*it_head);
                for (vector<int>::iterator jt_head = it_head; jt_head < candidates.end(); jt_head++)
                    combSum(combs, comb, candidates, jt_head, target-*it_head);
            }
        }
    };
    

Log in to reply
 

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