This problem looks busy at first, but the accepted solution is built around one steady invariant. For 526. Beautiful Arrangement, the solution in this repository is mainly a dynamic programming solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: dynamic programming, bit manipulation, backtracking.
The notes already sitting in the source point us in the right direction:
- backtrack
- time: O(#permutations), space: O(N)
Guide
When?
This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are backtrack, countArrangement, used.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Start from the smallest reliable state.
- Expand one legal move at a time.
- Cache, count, or merge information as soon as it becomes settled.
- Let the final stored value answer the original question.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(#permutations), space: O(N)
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//backtrack
02//Runtime: 536 ms, faster than 19.94% of C++ online submissions for Beautiful Arrangement.
03//Memory Usage: 6 MB, less than 71.95% of C++ online submissions for Beautiful Arrangement.
04//time: O(#permutations), space: O(N)
05class Solution {
06public:
07 int N;
08
09 void backtrack(int& count, vector<int>& perm, vector<bool>& used){
10 if(perm.size() == N){
11 count++;
12 }else{
13 for(int i = 0; i < N; i++){
14 //i+1: the value to be inserted
15 //perm.size()+1: the value's index in perm(1-based)
16 if(!used[i] && ((i+1) % (perm.size()+1) == 0 || (perm.size()+1) % (i+1) == 0)){
17 used[i] = true;
18 perm.push_back(i);
19 backtrack(count, perm, used);
20 used[i] = false;
21 perm.pop_back();
22 }
23 }
24 }
25 }
26
27 int countArrangement(int N) {
28 this->N = N;
29 int count = 0;
30 vector<int> perm;
31 vector<bool> used(N, false);
32 backtrack(count, perm, used);
33
34 return count;
35 }
36};
37
38//optimized backtracking
39//Runtime: 360 ms, faster than 37.06% of C++ online submissions for Beautiful Arrangement.
40//Memory Usage: 6.1 MB, less than 61.13% of C++ online submissions for Beautiful Arrangement.
41class Solution {
42public:
43 int N;
44
45 int backtrack(int cur, bitset<15>& used){
46 if(cur > N){
47 return 1;
48 }else{
49 int count = 0;
50
51 for(int i = 0; i < N; i++){
52 //i+1: the value to be inserted
53 //cur: the value's index in perm(1-based)
54 if(!used[i] && ((i+1) % cur == 0 || cur % (i+1) == 0)){
55 used[i] = 1;
56 count += backtrack(cur+1, used);
57 used[i] = 0;
58 }
59 }
60
61 return count;
62 }
63 }
64
65 int countArrangement(int N) {
66 this->N = N;
67 bitset<15> used;
68 return backtrack(1, used);
69 }
70};
71
72//recursion with memorization
73//Runtime: 88 ms, faster than 72.42% of C++ online submissions for Beautiful Arrangement.
74//Memory Usage: 9.3 MB, less than 20.58% of C++ online submissions for Beautiful Arrangement.
75class Solution {
76public:
77 int N;
78 map<pair<int, int>, int> memo;
79
80 int backtrack(int cur, bitset<15>& used){
81 pair<int, int> key = make_pair(cur, used.to_ulong());
82
83 if(cur > N){
84 return 1;
85 }else if(memo.find(key) != memo.end()){
86 return memo[key];
87 }else{
88 for(int i = 0; i < N; i++){
89 //i+1: the value to be inserted
90 //cur: the value's index in perm(1-based)
91 if(!used[i] && ((i+1) % cur == 0 || cur % (i+1) == 0)){
92 used[i] = 1;
93 memo[key] += backtrack(cur+1, used);
94 used[i] = 0;
95 }
96 }
97
98 return memo[key];
99 }
100 }
101
102 int countArrangement(int N) {
103 this->N = N;
104 bitset<15> used;
105 return backtrack(1, used);
106 }
107};
108
109//top-down DP/recursion with memorization
110//Runtime: 16 ms, faster than 88.26% of C++ online submissions for Beautiful Arrangement.
111//Memory Usage: 11.6 MB, less than 19.82% of C++ online submissions for Beautiful Arrangement.
112class Solution {
113public:
114 int N;
115 vector<vector<int>> dp;
116
117 int backtrack(int cur, bitset<15>& used){
118 int kused = used.to_ulong();
119 if(cur > N){
120 return 1;
121 }else if(dp[cur][kused] != -1){
122 return dp[cur][kused];
123 }else{
124 dp[cur][kused] = 0;
125
126 for(int i = 0; i < N; i++){
127 //i+1: the value to be inserted
128 //cur: the value's index in perm(1-based)
129 if(!used[i] && ((i+1) % cur == 0 || cur % (i+1) == 0)){
130 used[i] = 1;
131 dp[cur][kused] += backtrack(cur+1, used);
132 used[i] = 0;
133 }
134 }
135 // cout << "(" << cur << ", " << kused << "): " << dp[cur][kused] << endl;
136 return dp[cur][kused];
137 }
138 }
139
140 int countArrangement(int N) {
141 this->N = N;
142 bitset<15> used;
143 dp = vector<vector<int>>(N+1, vector<int>(1<<N, -1));
144 backtrack(1, used);
145 return dp[1][0];
146 }
147};Cost
Complexity
Time
O(#permutations), space: O(N)
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.