LeetCode 377. Combination Sum IV

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    unordered_map<int, int> m;
public:
    int combinationSum4(vector<int>& nums, int target) {
        if (target == 0) return 1;
        m[0] = 1;
        function<int(int)> dfs = [&](int target) {
            int ans = 0;
            for (const int& num : nums)
                if (target >= num) {
                    int t = target - num;
                    if (m.find(t) == m.end())
                        m[t] = dfs(t);
                    ans += m[t];
                }
            return ans;
        };
        return dfs(target);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        const int n = nums.size();
        vector<unsigned int> dp(target + 1);
        dp[0] = 1;
        for (int i = 1; i <= target; ++i)
            for (auto& num : nums)
                if (i >= num)
                    dp[i] += dp[i - num];
        return dp[target];
    }
};