Readme

3685.Subsequence-Sum-After-Capping-Elements

对于n个元素，问是否可以组合出和为k的方案，就是一个典型的有界背包问题，用o(n*k)的时间复杂度可解。大致算法是：

for (int i=0; i<nums.size(); i++) {
  for (int c=k; c>=1; c--) {
    dp[c] |= dp[c-nums[i];
  }
}

对于此题而言，对于每一个给定的x，我们要用nums里所有小于x的元素，以及剩余的元素当做x使用，问是否能组合出和为k的方案。我们暂时先不考虑第二种用法，即只用nums里小于x的元素。我们发现，随着x的增大，其实第一个for循环里可选的元素种类的上界也在单调增大，故总体这依然是一个o(n*k)可解的问题。

然后更深入地思考，我们将x从小到大遍历的时候，可以不断提升i，从而加入所有不超过x的新nums[i]，就可以不断更新dp。同时我们还需要考虑等于x的元素：因为capping的缘故，这样的元素有n-i个。此时我们需要考虑这额外的n-i个元素能否对于组成k有帮助。显然我们可以用同样的背包思想：

for (int j=1; j<n-i; j++) {
  if (dp[k-x*j]) {
     return true;
     break;
  }
}

注意，这个过程中我们只是判断是否能组合成k，不会去更新dp。我们始终保持dp[c]表示“能否用所有小于x的元素组成c”。这样，即使x变大，dp的定义依然适用。