From 1478c6b582e194a330e1f1f76e2b6c423be5e29d Mon Sep 17 00:00:00 2001
From: crupest <crupest@outlook.com>
Date: Tue, 13 Oct 2020 22:22:11 +0800
Subject: import(solutions): Add problem 401 .

---
 works/solutions/cpp/401.cpp | 68 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 68 insertions(+)
 create mode 100644 works/solutions/cpp/401.cpp

(limited to 'works/solutions/cpp/401.cpp')

diff --git a/works/solutions/cpp/401.cpp b/works/solutions/cpp/401.cpp
new file mode 100644
index 0000000..2618872
--- /dev/null
+++ b/works/solutions/cpp/401.cpp
@@ -0,0 +1,68 @@
+#include <string>
+#include <vector>
+
+using std::string;
+using std::vector;
+
+#include <array>
+#include <cstdio>
+
+const std::array<int, 4> hour_digits{1, 2, 4, 8};
+const std::array<int, 6> minute_digits{1, 2, 4, 8, 16, 32};
+
+class Solution
+{
+public:
+  template <int max, std::size_t size>
+  void dfs(const std::array<int, size> &digits, int total_count,
+           int rest_count, int start_index, int value,
+           std::vector<int> &result)
+  {
+
+    if (value >= max)
+      return;
+
+    if (rest_count == 0)
+    {
+      result.push_back(value);
+      return;
+    }
+
+    for (int i = start_index; i <= size - rest_count; i++)
+    {
+      dfs(digits, max, total_count, rest_count - 1, i + 1,
+          value + digits[i], result);
+    }
+  }
+
+  vector<string> readBinaryWatch(int num)
+  {
+    vector<string> results;
+
+    for (int i = (num > 6 ? num - 6 : 0); i <= (num > 4 ? 4 : num); i++)
+    {
+      std::vector<int> hours;
+      std::vector<int> minutes;
+      if (i == 0)
+        hours = {0};
+      else
+        dfs<12>(hour_digits, i, i, 0, 0, hours);
+      if (i == num)
+        minutes = {0};
+      else
+        dfs<60>(minute_digits, num - i, num - i, 0, 0, minutes);
+
+      for (auto hour : hours)
+      {
+        for (auto minute : minutes)
+        {
+          char buffer[6];
+          sprintf(buffer, "%d:%02d", hour, minute);
+          results.push_back(string(buffer));
+        }
+      }
+    }
+
+    return results;
+  }
+};
-- 
cgit v1.2.3