# Leetcode 解題速記 377. Combination Sum IV
###### tags: `LeetCode` `C++`
題敘:
---
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

測資範圍:
---
* `1 <= nums.length <= 200`
* `1 <= nums[i] <= 1000`
* `All the elements of nums are unique.`
* `1 <= target <= 1000`

解題筆記:
---
這題使用DP概念解題，方式類似走階梯問題，所有數字都可以使用無限次。以example 1為例，求總和為4的所有組合數，可以拆成1+3、2+2、3+1三種sum。因此，我們可以將這幾個sum的所有組合拆成 :
* 1 + [ target = 3 ] 的所有組合
* 2 + [ target = 2 ] 的所有組合
* 3 + [ target = 1 ] 的所有組合

首先開一個一維陣列保存所有target的組合數，基底條件DP[0]為1，從上述的分解中可以得到轉移方程式 :
`DP[i] = DP[i] + DP[i - nums中小於i的所有成員]`
由此traverse過整個nums vector後就可以得到所有target的組合數，直接access就可以獲得答案。

程式碼:
---

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        unsigned DP[1001] = {0};
        DP[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int j = 0; j < nums.size(); j++)
                if (nums[j] <= i)
                    DP[i] += DP[i - nums[j]];
        }
        return DP[target];
    }
};