Skip to content

526. Beautiful Arrangement 👍

  • Time: $O(n \cdot 2^n)$
  • Space: $O(2^n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  int countArrangement(int n) {
    return dfs(n, 1, string(n + 1, 'x'), {});
  }

 private:
  int dfs(int n, int num, string&& filled, unordered_map<string, int>&& mem) {
    if (num == n + 1)
      return 1;
    if (const auto it = mem.find(filled); it != mem.cend())
      return it->second;

    int count = 0;

    for (int i = 1; i <= n; ++i)
      if (filled[i] == 'x' && (num % i == 0 || i % num == 0)) {
        filled[i] = 'o';
        count += dfs(n, num + 1, move(filled), move(mem));
        filled[i] = 'x';
      }

    return mem[filled] = count;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
  public int countArrangement(int n) {
    final String filled = "x".repeat(n + 1);
    StringBuilder sb = new StringBuilder(filled);
    Map<String, Integer> mem = new HashMap<>();

    return dfs(n, 1, sb, mem);
  }

  private int dfs(int n, int num, StringBuilder sb, Map<String, Integer> mem) {
    if (num == n + 1)
      return 1;
    final String filled = sb.toString();
    if (mem.containsKey(filled))
      return mem.get(filled);

    int count = 0;

    for (int i = 1; i <= n; ++i)
      if (sb.charAt(i) == 'x' && (num % i == 0 || i % num == 0)) {
        sb.setCharAt(i, 'o');
        count += dfs(n, num + 1, sb, mem);
        sb.setCharAt(i, 'x');
      }

    mem.put(filled, count);
    return count;
  }
}