Link to the problem

Because of constraints, I understand that this question can be brute-forced. But I was thinking of an alternate approach and need further help whether it can be done this way or not.

So, assume the black squares are directed edges from the Row element to the column element. Hence, the problem requires us to remove outgoing edges (Rows) or incoming edges (Columns) of a node so that we are left with just K directed edges (including self-loops).

Now, we can have incoming and outgoing edge count for each node and find all the combinations which generate the sum K.

Now, the problem that is left is, although this gives us all the unique arrangements for the black squares possible, this does not take into account that different row or column selection can result in the same result.

For example, if you check the first sample input given, choosing both 1st row and 3rd Column, as well as just the 3rd column, generate the same black square arrangement.

So, the algorithm I described will give an output 4 instead of 5. How can it be corrected? Is this approach more efficient for larger constraints?

Thanks