Problem statement

https://binarysearch.com/problems/Chosen-N/

Solution

Use dp on subsets, where dp(mask, i) means that we already used columns from mask and currently on i-th row of matrix. Each time we check all bits which are equal to 1 in mask and if they are avaliable in M, we consider this candidate.

Complexity

Time complexity is O(n*2^n), because we have O(2^n) states (i is defined by mask uniquely) and O(n) transactions. Space complexity is O(2^n).

Code

class Solution:
    def solve(self, M):
        n = len(M)

        @lru_cache(None)
        def dp(mask, i):
            if i == -1: return 1
            ans = 0
            for j in range(n):
                if mask & (1<<j) and M[i][j] == 0:
                    ans += dp(mask ^ (1<<j), i - 1)
            return ans

        return dp((1<<n) - 1, n-1) % (10**9 + 7)