title: Dynamic Programming Question, selecting 1s in a 0-1 matrix such that each row and column contain exactly one 1
body: <p>Given a 0-1 square matrix, In how many ways can we select 1's such that each row and column contain exactly one 1?? </p>
  
  <p>I've implemented the following backtrack code for this problem:</p>
  
  <pre><code>    int countways(int A[][], int&amp; n, int row, vector&lt;bool&gt; columnselected ) {
           if(row == n)
                return 1;
           int result = 0;
           for( j = 0; j &lt; n ; ++j) {
                if(A[row][j]) {
                     if(!columnselected[j]) {
                          columnselected[j] = true;
                          result+ = countways(A, n, row+1, columnselected);
                          columnselected[j] = false;
                     }
                 }
           }
           return result;
       }
  </code></pre>
  
  <p>This is definitely not the best way to solve this problem. I can't enhance the solution by using a memoized version of the recursion since columnselected and row in every call to the recursion would be unique for every sub-problem.</p>
  
  <p>Please suggest a better approach to solve this problem, more like a dynamic programming solution, more efficient than this obvious solution.</p>