> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/301-400/combination-sum-iv.md).

# 377. Combination Sum IV

### Description

Given an array of **distinct** integers `nums` and a target integer `target`, return *the number of possible combinations that add up to* `target`.

The answer is **guaranteed** to fit in a **32-bit** integer.

### Constraints

* `1 <= nums.length <= 200`
* `1 <= nums[i] <= 1000`
* All the elements of `nums` are **unique**.
* `1 <= target <= 1000`

### Approach

### Links

* GeeksforGeeks
* [Leetcode](https://leetcode.com/problems/combination-sum-iv/)
* [ProgramCreek](https://www.programcreek.com/2014/07/leetcode-combination-sum-iv-java/)
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** nums = \[1, 2, 3], target = 4

**Output:** 7

**Explanation:**

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.
{% endtab %}

{% tab title="Example 2" %}
**Input:** nums = \[9], target = 3

**Output:** 0
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * Time complexity : O(T * N), T be the target value, and N be the 
 *    number of elements in the input array.
 * Space complexity : O(T)
 */

class Solution {
    private HashMap<Integer, Integer> memo;

    public int combinationSum4(int[] nums, int target) {
        // minor optimization
        // Arrays.sort(nums);
        memo = new HashMap<>();
        return combs(nums, target);
    }

    private int combs(int[] nums, int remain) {
        if (remain == 0)
            return 1;
        if (memo.containsKey(remain))
            return memo.get(remain);

        int result = 0;
        for (int num : nums) {
            if (remain - num >= 0)
                result += combs(nums, remain - num);
            // minor optimizaton, early stopping
            // else
            //     break;
        }
        memo.put(remain, result);
        return result;
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * Time complexity : O(T * N), T be the target value, and N be the 
 *    number of elements in the input array.
 * Space complexity : O(T)
 */

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

{% endtab %}
{% endtabs %}

### **Follow up**

*