算法1

(DP) $O(n*target)$

C++ 代码

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int f[1001];
        memset(f, 0, sizeof(f));
        f[0] = 1;
        for(int i = 1; i <= target; i++) {
            for(auto t : nums) {
                // 结果不溢出，中途结果可能溢出。。。绝了。。。
                // i-t>=0代表后续的i-t不会被计算，f[i] > INT_MAX说明f[target]不可能用到这个结果
                if(i - t >= 0 && f[i] + f[i-t] * 1L <= INT_MAX) f[i] += f[i-t];
                else break;
            }
        }
        return f[target];
    }
};

// 暴力枚举，o(2**n) = 2 ** 200, 超时
// DP?
// 
// f[i]: 和为id的组合方式
// 属性: 组合方式数量
// 状态转移: 
// f[i] = f[i-nums[k]] , k = [1..n]
// f[0] = 1
// 无后效性：比如1,2和2,1的和都为3, 即使后面插入相同的数，依然是不同的组合
// 时间复杂度o(n * target) = 2e5