Daily 09/09/2023: [377. Combination Sum IV](https://leetcode.com/problems/combination-sum-iv/)

# 1. Tóm tắt đề bài
Cho một mảng num các số nguyên khác nhau và số nguyên target, trả về số lượng tất cả tổ hợp có thể mà có tổng bằng target.

#### Giới hạn
- $1 \le nums.length \le 200$
- $1 \le nums[i] \le 1000$
- $1 \le target \le 1000$
- Tất cả các phần tử của nums đề đôi một khác nhau.

# 2. Tóm tắt lời giải
#### Cách tiếp cận và hướng giải
Các bài đếm thì đa số sử dụng quy hoạch động và bài này cũng không ngoại lệ, mọi người đọc triển khai quy hoạch động ở bên dưới.

# 3. Lời giải chi tiết
#### Thuật toán
Tạo mảng dp với dp[i] là số lượng tổ hợp các số có tổng bằng i.
Công thức quy hoạch động bài này đơn giản là $dp[i] = \Sigma _{nums[j] \le i} dp[i - nums[j]]$

#### Code
Hôm nay mình đổi gió code C++

class Solution {
public:
    unsigned int combinationSum4(vector<int>& nums, int target) {
        vector<unsigned int> dp(target + 1, 0);

        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (auto& x: nums) {
                if (i >= x) dp[i] += dp[i - x];  
            } 
        }
        return dp[target];
    }
};

#### Độ phức tạp
$O(n.target)$

# 4. Kết luận & Gọi ý mở rộng
Bài này là bài đếm bài bản, mọi người có thể luyện tập các dạng này.

[39. Combination Sum](https://leetcode.com/problems/combination-sum/)
[2787. Ways to Express an Integer as Sum of Powers](https://leetcode.com/problems/ways-to-express-an-integer-as-sum-of-powers/)