diff options
author | Nguyễn Gia Phong <vn.mcsinyx@gmail.com> | 2020-01-14 18:29:11 +0700 |
---|---|---|
committer | Nguyễn Gia Phong <vn.mcsinyx@gmail.com> | 2020-01-14 18:29:11 +0700 |
commit | a3dd2581ed4847670f81157091016c14ca18803d (patch) | |
tree | 3362ab15de119f1e75799f58715b7683e6bfd6ca /usth/MATH2.3/3/sum-set.cc | |
parent | 65b8ebda4c47fa27ac28899fb2b29097f445b6df (diff) | |
download | cp-a3dd2581ed4847670f81157091016c14ca18803d.tar.gz |
[usth/MATH2.3] Mathemate Discretely
Diffstat (limited to 'usth/MATH2.3/3/sum-set.cc')
-rw-r--r-- | usth/MATH2.3/3/sum-set.cc | 44 |
1 files changed, 44 insertions, 0 deletions
diff --git a/usth/MATH2.3/3/sum-set.cc b/usth/MATH2.3/3/sum-set.cc new file mode 100644 index 0000000..880fc6d --- /dev/null +++ b/usth/MATH2.3/3/sum-set.cc @@ -0,0 +1,44 @@ +#include <iostream> +#include <vector> + +using namespace std; + +void +backtrack (vector<size_t>& big, vector<size_t>& smol, size_t& n, size_t index) +{ + size_t sum = 0; + for (auto const& i : smol) + sum += i; + if (sum == n) + { + for (auto const& i : smol) + cout << i << " "; + cout << endl; + } + else + for (size_t i = index; i < big.size (); ++i) + if (sum + big[i] <= n) + { + smol.push_back (big[i]); + backtrack (big, smol, n, i + 1); + smol.pop_back (); + } +} + +int +main () +{ + size_t n; + size_t tmp; + vector<size_t> s; + + cin >> n; + for (size_t i = 0; i < n; ++i) + { + cin >> tmp; + s.push_back (tmp); + } + + vector<size_t> r; + backtrack (s, r, n, 0); +} |