###### tags: `Leetcode` `medium` `dynamic programming` `array` `python` `c++`

# 377. Combination Sum IV

## [題目連結:] https://leetcode.com/problems/combination-sum-iv/

## 題目:
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.

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

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

## 解題想法:
* Combination Sum系列題目:
* [39. Combination Sum](/W7B2e-02R7GECNxeVr0_vA)
* [40. Combination Sum II](/YxlQmfbsRV2-hX7xVVdtiw)
* [216. Combination Sum III](/1FxuhR0-QQKswHRda053fA)
* 此題為使用數組中的數組合為target
* 每個數字可重複使用
* 組合數字一樣，順序不一樣: 視為不同組合

* 使用DP:
* 定義: **dp[i]表示目標數為i的解的個數**
* dp=[0] * (target+1)
* init: dp[0]=1 ，組成合為0，啥都不選，一種解
* 雙迴圈:
* 第一圈:
* 目標數從i=0遍歷到target
* 第二圈:
* 對於每個i，遍歷nums
* 若i>= val of nums 則代表可以繼續拆分
* dp[i]+=dp[i-val]
* **解釋**:表示對於總和為(i-val)可以有dp[i-val]種組合後，加上val後可以組合為dp[i]
* 可以想成爬樓梯問題:
* 一次可以爬val階，則爬到i時的可能數

## Python:

class Solution(object):
    def combinationSum4(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        #dp[i]表示目標數為i的解的個數
        #從i遍歷到target
        #其中對於每個i 遍歷nums : 若i>=val 則代表可繼續拆分
        dp=[0]*(target+1)
        dp[0]=1
        for i in range(1,target+1):
            #想成爬樓梯問題: 一次可以爬val階 則爬到i時的可能數
            #可以想成: target=4 所以dp[4]=dp[3]+dp[2]+dp[1]
            for val in nums:
                if i>=val:
                    dp[i]+=dp[i-val]
        return dp[target]

result=Solution()
ans=result.combinationSum4(nums = [1,2,3], target = 4)
print(ans)

## C++:

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<unsigned int> dp(target+1,0);
        dp[0]=1;
        for(int val=1; val<=target; val++){
            for(const int num:nums){
                if(val-num>=0)
                    dp[val]+=dp[val-num];
            }
        }
        return dp[target];
    }
};

int main(){

    Solution res;
    vector<int> nums={1,2,3};
    int target=4;
    int ans=res.combinationSum4(nums,target);
    cout<<ans<<endl;
    return 0;
}