$(25$ points$)$

$($a$)(15$ points$)$ Describe a recursive algorithm that returns all possible

$nn$ binary arrays in which there is exactly one $1$ in each row and

each column. The following figure shows three examples of such $33$

binary arrays $($zeros are suppressed$).$

Figure $1$: Examples of $33$ binary arrays.

Describe your algorithm using a documented pseudocode. Make

sure that your algorithm is recursive; otherwise, you will lose most of

the points for problem $3.$ Make sure that your description is under$-$

standable.

$($b$)(10$ points$)$ Write down the recurrence for the running time of your

recursive algorithm in $($a$)$ with the boundary condition$($s$).$ Explain

your notations. Solve your recurrence from scratch to obtain the

the running time of your algorithm.