[LeetCode] Beautiful Arrangement

leetcode

Because the number N is smaller than 15, we can use recursion without worrying too much.

Below is the first solution I came up with, however, this contains side effect within recursive function.

I’m trying to think of the way without side effect. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    """
    @param N: The number of integers
    @return: The number of beautiful arrangements you can construct
    """
    def countArrangement(self, N):
        # Write your code here
        self.ans = 0
        def compute(unvisited, index):
            if len(unvisited) == 0:
                self.ans += 1
                return
            for i in range(len(unvisited)):
                s = unvisited[i]
                if s % index == 0 or index % s == 0:
                    unvisit = unvisited[:i] + unvisited[i+1:]
                    compute(unvisit, index + 1)

        n = list(range(1, N + 1))
        compute(n, 1)
        return self.ans