From a3dd2581ed4847670f81157091016c14ca18803d Mon Sep 17 00:00:00 2001
From: Nguyễn Gia Phong <vn.mcsinyx@gmail.com>
Date: Tue, 14 Jan 2020 18:29:11 +0700
Subject: [usth/MATH2.3] Mathemate Discretely

---
 usth/MATH2.3/3/sum-set.cc | 44 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 44 insertions(+)
 create mode 100644 usth/MATH2.3/3/sum-set.cc

(limited to 'usth/MATH2.3/3/sum-set.cc')

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);
+}
-- 
cgit 1.4.1