LC-2741 Medium LeetCode

2741. Special Permutations

Array Dynamic Programming Bit Manipulation Bitmask

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 28% Topics: Array, Dynamic Programming, Bit Manipulation, Bitmask

Reading material

Arrays & Hashing 12 min 1-D Dynamic Programming 16 min Bit Manipulation 10 min

Reference solution (spoiler · python)

# Time:  O(n^2 * 2^n)
# Space: O(n * 2^n)

# backtracking, memoization
class Solution(object):
    def specialPerm(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        MOD = 10**9+7
        def backtracking(i, mask):
            if mask == (1<<len(nums))-1:
                return 1
            if lookup[i+1][mask] == -1:
                total = 0
                for j in xrange(len(nums)):
                    if mask&(1<<j):
                        continue
                    if not (i == -1 or nums[i]%nums[j] == 0 or nums[j]%nums[i] == 0):
                        continue
                    total = (total+backtracking(j, mask|(1<<j)))%MOD
                lookup[i+1][mask] = total
            return lookup[i+1][mask]

        lookup = [[-1]*(1<<len(nums)) for _ in xrange(len(nums)+1)]
        return backtracking(-1, 0)

Solution from kamyu104/LeetCode-Solutions · MIT