Python backtracking solution with memoization ~


  • 0
    L
    class Solution(object):
        def countArrangement(self, N):
            # memoization
            self.mymap = {}
            
            used = [False] * (N + 1)
            return self.backtracking(1, used, N)
            
        def backtracking(self, pos, used, N):
            # number of beautiful arrangements we can have from now on
            count = 0   
            
            # transform bool array into integer to store it in hash table
            key = self.to_string(used)
            
            # check if we already have the answer
            if key in self.mymap:
                return self.mymap[key]
            
            # if at the end
            if pos == N + 1:
                return 1
            
            for i in range(1, N + 1):
                if not used[i] and (i%pos == 0 or pos%i == 0):
                    used[i] = True
                    count += self.backtracking(pos + 1, used, N)
                    used[i] = False
            
            self.mymap[key] = count
            return count
        
        # transform function
        def to_string(self, arr):
            ans = 0
            for i in arr:
                if i: ans |= 1
                ans <<= 1
            return ans
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.