class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
int n = nums.size();
int f[target + 1] = {0};
f[0] = 1;
for (int i = 0; i <= target; ++i) {
if (f[i] == 0) {
continue;
}
for (int j = 0; j < n; ++j) {
int t = i + nums[j];
if (t <= target) {
f[t] += f[i];
}
}
}
return f[target];
}
};
My 0ms C++ DP solution


Wow, your solution is better than
My 3ms Java DP solution
.
Your complexity isO(n*target)
but that solution's complexity isO(max{Array.sort(), n*target})
.
So as the fastest java sort algorithm, the complexity isO(n*logn)
and as a result, your solution is faster than that solution whenlogn > target
.Thumb up~