# 377. Combination Sum IV

### Leetcode

<https://leetcode.com/problems/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 test cases are generated so that the answer can fit in a **32-bit** integer.

&#x20;

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

### 解答 <a href="#ti-jie" id="ti-jie"></a>

* **方法一 - DP**

我們先定義 `dp[i]` 代表的是當 `target = i` 時，所有可能組合的數量

例如：`nums = [1,2,3], target = 4`

`dp[1] = 1` 代表 `target = 1` 時總共有一種可能，組合為 `(1)`&#x20;

`dp[2] = 2` 代表 `target = 2` 時總共有兩種可能，組合為 `(1, 1)` 及 `(2)`&#x20;

而下一步需要找出 DP 的狀態轉換方程，這裡一樣以上面的例子來看

例如：`nums = [1,2,3], target = 4`，要組成 `target = 4` 的組合，有以下這幾種可能：

* 元素 `3` + `dp[1]`

  組合：`(3,1)`
* 元素 `2` + `dp[2]`

  組合：`(2,1,1),(2,2)`
* 元素 `1` + `dp[3]`

  其中的 `dp[3]` 又可以拆解為：

  * `1 + dp[2]`

    組合：`(1,1,1),(1,2)`
  * `2 + dp[1]`

    組合：`(2,1)`
  * `3 + dp[0]`

    組合：`(3)`&#x20;

  組合：`(1,1,1,1),(1,1,2),(1,2,1),(1,3)`

所以總共有 1 + 2 + 4 = 7 種組合

```javascript
var combinationSum4 = function (nums, target) {
    // 初始化每個 target 的 dp 為 0
    const dp = Array.from({ length: target + 1 }, () => 0);
    dp[0] = 1;

    for (let i = 1; i <= target; i++) {
        for (let j = 0; j <= nums.length; j++) {
            const value = nums[j];
            // 如果 target 大於等於元素的話，才有辦法湊出來
            if (i >= value) {
                dp[i] += dp[i - value];
            }
        }
    }

    return dp[target];
}
```

DP 的初始條件：

1. 一開始每個 `dp[i]` 都等於 0，因為有可能湊不到 `target`&#x20;

   例如：`nums = [5], target = 2`，`dp[1]` 及 `dp[2]` 很明顯都是 0
2. `dp[0] = 1`

   例如：`nums = [3], target = 3`，`dp[3]` 唯一的組合只有 `(3)` 這一種，所以當元素與 target 值一樣時，`dp[0]` 定為 `1`

**參考資料**

{% embed url="<https://hackmd.io/@GlycerinLOL/S11B1j5pc>" %}
