类似完全背包

$ 时间复杂度O(NM),空间复杂度O(M) $

参考文献

lc究极班

AC代码

class Solution {
public:
    int combinationSum4(vector<int>& nums, int m) {
        vector<long long> f(m + 1, 0);
        f[0] = 1;//初始化
        for (int j = 0 ; j <= m ; j ++){
            for (int i = 0 ; i < nums.size() ; i ++){
                int v = nums[i];
                if (j >= v)
                    f[j] = (f[j] + f[j - v] % INT_MAX);//防止溢出
            }
        }
        return f[m];
    }
};