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!