Combination Sum IV

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3] target = 4

The possible combination ways are: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

Follow up:

What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers?

Tips:

原题：比较简单的DP，初始化是result[0] = 1; 转移公式是 result[i] += result[i - num]。

Follow up：

加一个visted吧，一个数只能用一次

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.

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.

Code：

public class Solution {
    public int combinationSum4(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] result = new int[target + 1];
        result[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int num : nums) {
                if (num <= i) {
                    result[i] += result[i - num];
                }
            }
        }
        return result[target];
    }
}