What if negative numbers are allowed in the given array?


  • 11
    Y

    Anyone has concise solution for this case? If we still need to use the same code, it will lead to infinite loop? how to fix it?


  • 20

    I think if there are negative numbers in the array, we must add a requirement that each number is only used one time, or either positive number or negative number should be used only one time, otherwise there would be infinite possible combinations.
    For example, we are given:
    {1, -1}, target = 1,
    it's obvious to see as long as we choose n 1s and (n-1) -1s, it always sums up to 1, n can be any value >= 1.


  • 0
    D

    Thanks! this make sense


  • 0

    @vcoderld

    I think in this case the DP solution won't work any more because each time we are trying to add one more number on top of existing combinations. We need to know what numbers are already in the combinations.
    Looks like only recursively finding out all combinations will give us the correct answer.


  • 0

    @soamaaazing
    I don't think recursion will work if we don't add any extra requirement.
    Basically, DP is to memorize the results of sub-problems, which is exactly what recursion will re-calculate instead. They are substantially the same. So if one of the them is not working, neither is the other.

    For this problem itself, still use the {-1, 1} example, if we can use any number more than one time, it actually equals to we are given {all negative integers, 0, all positive integers}, ie we are given an array with infinite length because -1 can be used to compose all negative integers and similarly for 1. So there will be infinite number of combinations.


  • 2

    @vcoderld
    Thanks for your explanation. I believe I didn't express my idea clearly: by saying "in this case", I meant adding the the condition that "if there are negative numbers in the array, we must add a requirement that each number is only used one time".
    So again, I think in this case DP may not be able to solve the problem. Do you agree?


  • 0
    O

    Is there a polynomial solution for the negative case??


Log in to reply
 

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