Time:O(n \cdot 2^n) Space:O(2^n) C++ 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>&& memo) { if (num == N + 1) return 1; if (memo.count(filled)) return memo[filled]; 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(memo)); filled[i] = 'x'; } return memo[filled] = count; } }; JAVA class Solution { public int countArrangement(int N) { final String filled = "x".repeat(N + 1); StringBuilder sb = new StringBuilder(filled); Map<String, Integer> memo = new HashMap<>(); return dfs(N, 1, sb, memo); } private int dfs(int N, int num, StringBuilder sb, Map<String, Integer> memo) { if (num == N + 1) return 1; final String filled = sb.toString(); if (memo.containsKey(filled)) return memo.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, memo); sb.setCharAt(i, 'x'); } memo.put(filled, count); return count; } }