Python Backtracking + memoization


  • 0

    Memoize the count at the given index (i) for each unique set of remaining numbers. I've used a string of 1's and 0's to be hashed instead of creating tuples or what not.

        def countArrangement(self, N):
    
            def rain(valid, counts, ind, N, used):
                if ind > N: return 1 # end
                s = ''.join(used) # remainder string to be hashed
                if s in counts[ind]: return counts[ind][s] # if in memo, return memoized value
                cnt = 0
                for i in valid[ind]:
                    _i = i-1
                    if used[_i] == '0': continue
                    used[_i] = '0' # backtracking
                    cnt += rain(valid, counts, ind+1, N, used)
                    used[_i] = '1'
                counts[ind][s] = cnt # memoize
                return cnt
                
            
            if not N: return 0
            valid, counts = collections.defaultdict(list), collections.defaultdict(dict)
            # generating valid entries for each position
            for i in range(1, N+1):
                for n in range(1, N+1):
                    if i % n == 0 or n % i == 0: valid[i].append(n)
            return rain(valid, counts, 1, N, ['1' for _ in range(N)])
    

Log in to reply
 

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