CF 687C

• @ 背包问题升级：n个硬币组合成面值为k，然后问其子集可以组成多少种面值。

• @ dp[i][j][k] 表示前i个物品组成面值为j时候其子集为k，这里看起来似乎有个问题
  就是不同的组合之间会不会交叉的问题，其实很简单，由背包的转移状态可以知道
  dp[j]|= dp[j - coin[i]] 可以知道，只有后面的面值可能才能转移成功，这就表明即使
  是重合，也是合法的那一部分。

#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
const int maxn = 507;
int coin[maxn], n, m;
int dp[maxn][maxn];
int main(int argc, char const *argv[])
{
    std::ios::sync_with_stdio(false);
    std::cin >> n >> m;
    int sum = 0;
    for(int i = 1; i <= n; i ++){
        std::cin >> coin[i];
        sum += coin[i];
    }
    dp[0][0] = 1;
    for(int i = 1; i <= n; i ++){
        for(int j = m; j >= coin[i]; j --){
            for(int k = 0; k <= j; k ++){
                if(k >= coin[i]) dp[j][k] |= dp[j - coin[i]][k - coin[i]];
                dp[j][k] |= dp[j - coin[i]][k]; 
            }
        }
    }
    std::vector<int> ans;
    for(int i = 0; i <= m; i ++){
        if(dp[m][i]) ans.push_back(i);
    }
    std::cout << ans.size() << '\n';
    for(int i = 0; i < ans.size(); i ++){
        if(i) std::cout << ' ';
        std::cout << ans[i];
    }
    std::cout << std::endl;
    return 0;
}