Money Sums

题目描述

You have n coins with certain values. Your task is to find all money sums you can create using these coins.

输入

The first input line has an integer n: the number of coins.
The next line has n integers x1,x2,...,xn: the values of the coins.
Constraints
1 ≤ n ≤ 100
1 ≤ xi ≤ 1000

输出

First print an integer k: the number of distinct money sums. After this, print all possible sums in increasing order.

样例输入

4
4 2 5 2

样例输出 

9
2 4 5 6 7 8 9 11 13

思路：题目是要求n个数能组成的所有和。一一枚举的话有2^n-1，肯定是不可能的。我们可以使用动态规划来优化，用一个bool数组dp来表示组成的和可以为i，然后枚举每一个数字，枚举每一个可能的和，如果去掉这一个数的和存在，那么可以在此基础上添加这个数。

关于遍历的顺序，这里说明一下，为什么是从最大值开始递减？其实可以先尝试一下从0开始递增，如果和（dp[j])存在，那么给原来的和加上这个数(dp[j+a[i]])也肯定存在。但是这样做有一个错误，就是在我们判断完dp[j+a[i]]存在，给他做完标记后，由于我们是从前往后遍历的，我们下一次会遍历到更大的dp[j+a[i]]，导致会在和为j的基础上重复添加a[i]。而AC代码中我们使用的是从后往前遍历，先判断小的和是否满足，然后加上这个数后的和一定会比之前的数大，我们就再本轮遍历时就不会再访问到了。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=200010;
int x[110];
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int n;cin>>n;int sum=0;for (int i=1;i<=n;i++){cin>>x[i];sum+=x[i];}vector<bool>dp(sum+1,false);dp[0]=true;for (int i=1;i<=n;i++){for (int j=sum;j>=x[i];j--){if (dp[j-x[i]])dp[j]=true;}}set<int>s;for (int i=1;i<=sum;i++){if(dp[i])s.insert(i);}cout<<s.size()<<'\n';for (int i:s)cout<<i<<' ';
}