From 189313e0f901339bdeb80013772564e360e3013e Mon Sep 17 00:00:00 2001 From: crupest Date: Thu, 15 Oct 2020 15:48:13 +0800 Subject: import(solutions): Add problem 526 . --- works/solutions/cpp/526.cpp | 29 +++++++++++++++++++++++++++++ 1 file changed, 29 insertions(+) create mode 100644 works/solutions/cpp/526.cpp (limited to 'works/solutions/cpp') diff --git a/works/solutions/cpp/526.cpp b/works/solutions/cpp/526.cpp new file mode 100644 index 0000000..19f445f --- /dev/null +++ b/works/solutions/cpp/526.cpp @@ -0,0 +1,29 @@ +#include + +using std::vector; + +class Solution { +public: + void dfs(int N, int index, bool *num_used, int &result) { + if (index > N) { + result += 1; + return; + } + + for (int num = 1; num <= N; num++) { + if (!num_used[num] && (num % index == 0 || index % num == 0)) { + num_used[num] = true; + dfs(N, index + 1, num_used, result); + num_used[num] = false; + } + } + } + + int countArrangement(int N) { + bool *num_used = new bool[N + 1]{false}; + int result = 0; + dfs(N, 1, num_used, result); + delete[] num_used; + return result; + } +}; -- cgit v1.2.3 From 69b9b2269b51305f64ab47c260531af286407faf Mon Sep 17 00:00:00 2001 From: crupest Date: Thu, 15 Oct 2020 18:14:37 +0800 Subject: import(solutions): Add peoblem 46 . --- works/solutions/cpp/46.cpp | 34 ++++++++++++++++++++++++++++++++++ 1 file changed, 34 insertions(+) create mode 100644 works/solutions/cpp/46.cpp (limited to 'works/solutions/cpp') diff --git a/works/solutions/cpp/46.cpp b/works/solutions/cpp/46.cpp new file mode 100644 index 0000000..bfb3c83 --- /dev/null +++ b/works/solutions/cpp/46.cpp @@ -0,0 +1,34 @@ +#include + +using std::vector; + +class Solution { +public: + void dfs(const vector &nums, vector ¤t, bool *num_used, + vector> &result) { + if (current.size() == nums.size()) { + result.push_back(current); + return; + } + + for (int i = 0; i < nums.size(); i++) { + if (!num_used[i]) { + num_used[i] = true; + current.push_back(nums[i]); + dfs(nums, current, num_used, result); + current.pop_back(); + num_used[i] = false; + } + } + } + + vector> permute(vector &nums) { + vector current; + vector> result; + bool *num_used = new bool[nums.size()]{false}; + dfs(nums, current, num_used, result); + delete[] num_used; + + return result; + } +}; -- cgit v1.2.3