 # Binary matrix with given row and column sum

Hello everyone, I was trying one problem but was unable to get the solution of this problem , here is the problem.

Given N (number of rows) and M(number of columns), find the total number of binary matrices (containing only 0s and 1s) where sum of ith row of this matrix should be Ri and the sum of jth Column of the matrix should be Cj.

Input format : First line contains number of test cases( T ). Description of each test case is as follows, first line of each test case contains N and M number of rows and columns respectively. next line contains N integers ith integer denotes the sum if the ith row(Ri) next line contains M integers where jth integer denotes the sum of jth column(Cj)

Constraints: 1<=T<=10
1<=N <=8
1<=M<=8
0<=Ri<=M
0<=Cj<=N

Output format: (1) If there is only one solution satisfying the given criteria print this Matrix .
(2) Otherwise print the total number of possible solution satisfying the given condition.

Sample Input:

3
4 4
1 1 1 1
1 1 1 1
3 3
3 2 3
3 3 2
4 4
1 2 1 3
3 2 2 1

Sample output:
24
1 1 1
1 1 0
1 1 1
0

Explanation: In the first test case you can put only one matrix in each row and each column so in first row there are 4 possibilities in second 3 possibilities in third 2 possibilities and in the last row there is only one remaining place so answer is 4 * 3 * 2 * 1=24
In second test case there is only one possible arrangement so print the corresponding matrix.
In the third there is no possible arrangement.

1 Like

looking at the constranints i think we can use brute-force and back-tracking to solve it , plz send the problem link.

1 Like

Sorry, but I am unable to open the link right now but don’t you think that brute force may give time out? By the way thanks.

here is the solution

2 Likes