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.

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.

Example 2:

Input: nums = [9], target = 3
Output: 0

解答

• 方法一 - DP

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

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

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

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

而下一步需要找出 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)

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

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

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

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

2. dp[0] = 1

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

參考資料

Leetcode 解題速記 377. Combination Sum IV - HackMDHackMD