For test case [[2, 18]], why my code failed????


  • 0
    T
    class Solution {
    public:
    void helper(vector<vector<int> >& result, vector<int>& temp, int k, int n, int start)
    {
        if(0 == k)
        {
            if(n == 0)
                result.push_back(temp);
            return;
        }
        for(int i = start; i <= 9; i++)
        {
            if(i <= n)
            {
                temp.push_back(i);
                helper(result, temp, k - 1, n - i, i);//last parameter should be i instead of i + 1??????
                temp.pop_back();
            }
        }
    }
    vector<vector<int> > combinationSum3(int k, int n) {
        vector<vector<int> > result;
        if(n == 0 || k == 0)
            return result;
        vector<int> temp;
        helper(result, temp, k, n, 1);
        return result;
    }
    };
    

    For test case (2, 18), the answer is [[9, 9]], which means numbers could be repeated. Thus, when calling helper function recursively, the start number should be the current number i instead of i+1.
    However, my code would fail at (2, 18). If I change my code to i+1, it gets passed.

    Could anyone know why this happen? Thanks for your input!


  • 0
    Z
    This post is deleted!

  • 0
    Z
    This post is deleted!

  • 1
    Z

    Well, I have to say you have made a mistake :-). The result must be: your output is [[9,9]], but it is expected as [[ ]]. Please double check, your code should be:

    helper(result, temp, k - 1, n - i, i + 1);


  • 0
    L

    I had similar problem here. if we use i, in the next recursion, i is also starting from i to 9. Agree with zjchenRice.


Log in to reply
 

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