Follow up: what if input contains zero and negative numbers?


  • 0
    L

    I came across this follow up question in an interview after I solved the "all positive input" version using recursion. The interviewer asked me what should I consider incase the input array contains negative numbers, but he did not ask me to write the code.

    First thing I noticed is that if we use the same approach, the recursion call will never reach the base case, hence result in an infinite loop.

    My answer was to generate all combinations of negative numbers, and add the absolute value of sum of negative combination to the target, and solve each subproblem using the same approach as CombinationSum. Here is an example:

    input:

    candidate: [-1, -2, -3, 10, 1, 2, 7, 6, 1, 5],
    target: 8

    First step: generate all combination (according to the rules specified in the problem):

    [] : 0
    
    [-1] : 1
    
    [-2] : 2
    
    [-3] : 3
    
    [-1, -2] : 3
    
    [-1, -3] : 4
    
    [-2, -3] : 5
    
    [-1, -2, -3] : 6
    

    There are 8 possible combinations of negative input value, but there are only 7 possible negative sum values: namely 0, 1, 2, 3, 4, 5, 6. Therefore we need to solve 7 subproblems with the input:

    [10, 1, 2, 7, 6, 1, 5], target : 8, 9, 10, 11, 12, 13, 14

    Last step is to combine them together.

    COMMENT:
    This follow up only makes sense in CombinationSum_II, because in CombinationSum_I, you can pick each number multiple times, which leads to infinite number of possible solutions. Also zero does not make any sense either, because you can add infinite number of zeros in the result.

    QUESTIONS:
    Any one can comment on this approach? Is this approach correct? Is there a better approach?

    Thanks!


  • 0
    W

    It depends on your algorithm. If your algorithm is the same as the common DFS version, where (target < 0) is used as a return condition (base case to end recursion for invalid trials), you can loose it to (target < negSum), where negSum is the total sum of all negative numbers in the collections (thus the most negative you can get with those numbers).
    Your solution might save some iterations, might not; but this loosing method could be less complicated. (OJ does not allow us to test collections with 0 included)


  • 0
    A

    @lzb700m You are wrong. Zero and Negative numbers make little difference. The same recursive solution works well, you just need to remove the "target >= 0" check in recursion.

    class Solution {
    public:
        void rc(vector<int>& c, int t, int e, vector<int>& p, vector<vector<int>>& o) {
            for (int l = INT_MAX; e >= 0; e--) {
                if (c[e] == l) continue;
                l = c[e];
                p.push_back(l);
                if (!(t-l)) o.push_back(p);
                rc(c, t-l, e-1, p, o);
                p.pop_back();
            }
        }
        vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
            sort(candidates.begin(), candidates.end());
            vector<vector<int>> o;
            vector<int> p;
            rc(candidates, target, candidates.size()-1, p, o);
            return o;
        }
    };
    

    Run Code Result:

    Your input
    [-1,-1,0,0,1,1,2,5]
    8

    Your answer
    [[5,2,1],[5,2,1,1,0,0,-1],[5,2,1,1,0,-1],[5,2,1,1,-1],[5,2,1,0],[5,2,1,0,0]]

    Expected answer
    [[-1,0,0,1,1,2,5],[-1,0,1,1,2,5],[-1,1,1,2,5],[0,0,1,2,5],[0,1,2,5],[1,2,5]]


Log in to reply
 

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