> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/recursion-and-backtracking/subsequence-pattern/377.-combination-sum-iv.md).

# 377. Combination Sum IV

## Problem Statement

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

The test cases are generated so that the answer can fit in a **32-bit** integer.

 

**Example 1:**

<pre><code><strong>Input: nums = [1,2,3], target = 4
</strong><strong>Output: 7
</strong><strong>Explanation:
</strong>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.
</code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [9], target = 3
</strong><strong>Output: 0
</strong></code></pre>

&#x20;

**Constraints:**

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

&#x20;

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

## Intuition

```
Approach:

Start a for loop from start and go till the end, picking each element

Hence no need for tracking index

```

### Links

<https://leetcode.com/problems/combination-sum-iv/description/?envType=daily-question&envId=2023-09-09>

### Video Links

<https://www.youtube.com/watch?v=IQeEhERcSbQ&t=402s&ab_channel=AryanMittal>

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    vector<long long> dp; // Use long long instead of int
    long long find_comb(vector<int>& nums, int target) {
        if (target == 0)
            return 1;

        if (target < 0)
            return 0;

        if (dp[target] != -1)
            return dp[target];

        long long ans = 0; // Use long long
        for (int i = 0; i < nums.size(); i++)
            ans += find_comb(nums, target - nums[i]);

        return dp[target] = ans;
    }

    int combinationSum4(vector<int>& nums, int target) {
        dp = vector<long long>(target + 1, -1); // Adjust the size of the dp array
        return static_cast<int>(find_comb(nums, target)); // Convert the result to int
    }
};

```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###