f[i] 表示凑出 i 的所有方案数。按照每种方案的最后一个数是什么划分子问题。当最后一个数是 a[j] 时，考虑如何凑出 i - a[j]，方案的数量等于 f[i - a[j]]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
 public:
  int combinationSum4(vector<int>& nums, int m) {
    vector<unsigned> f(m + 1);
    // f[i] 表示凑出 i 的所有方案数
    f[0] = 1;
    for (int i = 1; i <= m; i++) {
      for (auto j : nums) {
        if (i >= j) {
          f[i] += f[i - j];
        }
      }
    }
    return f[m];
  }
};