fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int maxN = 1e5;
  4. signed main(){
  5. 	cin.tie(0);
  6. 	ios::sync_with_stdio(false);
  7. 	int n;
  8. 	cin >> n;
  9. 	vector<int> vec(n + 1);
  10. 	for(int i = 1; i <= n; i++){
  11. 		cin >> vec[i];
  12. 	}
  13. 	vector<vector<bool>> dp(n + 1, vector<bool>(maxN + 1, 0));
  14. 	dp[0][0] = true;
  15. 	for(int i = 1; i <= n; i++){
  16. 		for(int j = 0; j <= maxN; j++){
  17. 			if(j - vec[i] < 0){
  18. 				dp[i][j] = dp[i - 1][j];
  19. 				continue;	
  20. 			} 
  21. 			dp[i][j] = (dp[i - 1][j - vec[i]] || dp[i - 1][j]);
  22. 		}
  23. 	}
  24. 	set<int> possible;
  25. 	for(int i = 1; i <= maxN; i++){
  26. 		if(dp[n][i]) possible.insert(i);
  27. 	}
  28. 	cout << possible.size() << endl;
  29. 	for(auto num: possible){
  30. 		cout << num << " ";
  31. 	}
  32.  
  33. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
4
4 2 5 2
stdout
copy 
9
2 4 5 6 7 8 9 11 13
https://ideone.com/fc4i8m
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!