https://leetcode.com/problems/beautiful-arrangement

We can use usual backtracking and count answer, but potentially it is quite expensive, like O(n!).

Alternative approach is to use dynamic programming with bitmasks. The idea is to use function dfs(bm, pl), where:

  1. bm is binary mask for visited numbers.
  2. pl is current place we want to fill. Idea is to start from the end, and fill places in opposite direction, because for big numbers we potentially have less candidates. (if we start form pl = 0 and go in increasing direction, then it is also will work fine, like 120ms vs 60ms)

Now, let us discuss how dfs(bm, pl) will work:

  1. If we reached place 0 and procces was not interrupted so far, it means that we find beautiful arrangement.
  2. For each number 1, 2, ..., N we try to put this number on place pl: and we need to check two conditions: first, that this place is still empty, using bitmask and secondly that one of the two properties for beutiful arrangement holds. In this case we add dfs(bm^1<<i, pl - 1) to final answer.
  3. Finally, we run dfs(0, N): from the last place and with empty bit-mask.

Complexity: First of all, notice that we have 2^N possible options for bm, N possible options for pl. But in all we have only 2^N states: pl is uniquely defined by number of nonzero bits in bm. Also we have N possible moves from one state to another, so time complexity is O(N*2^N). Space complexity is O(2^N).

class Solution:
    def countArrangement(self, N):
        @lru_cache(None)
        def dfs(bm, pl):
            if pl == 0: return 1
                
            S = 0
            for i in range(N):
                if not bm&1<<i and ((i+1)%pl == 0 or pl%(i+1) == 0):
                    S += dfs(bm^1<<i, pl - 1)
            return S
                
        return dfs(0, N)

Remark: this is so-called dynamic programming on subsets problem, which has similar ideas with TSP (travelling salesman problem). Usually you can recoginze these problems if dimension of data is around 10-20. Here is the list of similar problems on leetcode I found so far:

Problem 465 Optimal Account Balancing

Problem 473 Matchsticks to Square

Problem 698 Partition to K Equal Sum Subsets

Problem 847 Shortest Path Visiting All Nodes]

Problem 854 K-Similar Strings

Problem 943 Find the Shortest Superstring

Problem 1434 Number of Ways to Wear Different Hats to Each Other

Problem 1494 Parallel Courses II https://leetcode.com/problems/parallel-courses-ii/discuss/710229/Python-Short-DP-with-Binary-Masks-O(n2*2n)-explained

Problem 1655 Distribute Repeating Integers

Problem 1659 Maximize Grid Happiness https://leetcode.com/problems/maximize-grid-happiness/discuss/936467/Python-Short-and-clean-dp-with-diagram-expained

Problem 1681. Minimum Incompatibility https://leetcode.com/problems/minimum-incompatibility/discuss/961969/Python-True-O(nn2n)-bit-dp-explained

Please let me know, if you know more similar dynamic programming with sets problems!

If you like the solution, you can upvote it on leetcode discussion section: Problem 0526