[每日一题] 377.组合总和Ⅳ

2024 年 04 月 22 日

95 次浏览

1457字数

> https://leetcode.cn/problems/combination-sum-iv/description/?envType=daily-question&envId=2024-04-11

看到组合数下意识先写了个 DFS ：

```c++
class Solution {
public:
    int combinationSum4(std::vector<int>& nums, int target) {
        int n = nums.size();

int res = 0;
        
        std::function<void(const int&)> dfs = [&] (const int &sum) {
            if (sum == target) {
                res += 1;
                return;
            }
            
            for (int i = 0; i < n; i++) {
                if (sum + nums[i] <= target)
                    dfs(sum + nums[i]);
            }
        };
        
        dfs(0);
        return res;
    }
};
```

直接的 DFS 显然会超时，于是想着加个记忆化搜索：

```c++
class Solution {
public:
    int combinationSum4(std::vector<int>& nums, int target) {
        int n = nums.size();

std::vector<int> dp(target + 1, -1);
        dp[0] = 1;

std::function<int(const int&)> dfs = [&] (const int &sum) {
            if (dp[sum] != -1)
                return dp[sum];

for (int i = 0; i < n; i++) {
                if (sum - nums[i] >= 0) {
                    int previousCount = dfs(sum - nums[i]);
                    dp[sum] = dp[sum] == -1 ? previousCount : dp[sum] + (previousCount == -1 ? 0 : previousCount);
                }
            }

return dp[sum];
        };

int res = dfs(target);
        return res > 0 ? res : 0;
    }
};
```

还是超时。重新审视题目发现是明显的 DP 题，有以下递推式：

```
dp[i] += dp[i - num] for num in nums if i - num > 0
```

边界条件为 `dp[0] = 1` ，即有且仅有不选择任何元素时元素和为 0 。

因此最终结果如下：

```c++
class Solution {
public:
    int combinationSum4(std::vector<int>& nums, int target) {
        std::vector<int> dp(target + 1);
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (const auto &num : nums) {
                if (i >= num && dp[i - num] < INT_MAX - dp[i])
                    dp[i] += dp[i - num];
            }
        }

return dp[target];
    }
};
```

- 时间复杂度：$O(target \times n)$ ，其中 $target$ 为目标值，$n$ 为数组 $nums$ 的长度。
- 空间复杂度：$O(target)$ 。

最后修改：2024 年 05 月 06 日