# 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?

**Credits:**

Special thanks to @pbrother for adding this problem and creating all test cases.

**Code**

class Solution {
    int count = 0;
    int currSum = 0;
    int target;
    int[] nums;

    public int combinationSum4(int[] nums, int target) {
        // corner case
        if(nums == null) return 0;
        
        // init the global
        this.nums = nums;
        this.target = target;
        bt();
        return count;
    }
    
    public void bt() {
        if(currSum == target) {
            count++;
            return;
        }
        
        //  > target
        if(currSum > target) return;
        
        // < target
        for(int num : nums) {
        
            // add num to sum
            currSum += num;
            
            // backtracking
            bt();
            
            // remove num from sum
            currSum -= num;
        }
    }
}

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        if not nums or target <= 0:
            return 0

        table = dict()

        def dfs(cur):
            nonlocal nums, table
            if cur < 0:
                return 0
            if cur in table:
                return table.get(cur)

            res = 0
            for num in nums:
                if num > cur:
                    break
                res += dfs(cur - num)
            table[cur] = res

            return table[cur]

        nums.sort()
        table[0] = 1

        return dfs(target)