Print unique rows in a boolean matrix

Given a matrix of 0 and 1, print all unique rows of it.
There is standard technique to check if a particular pattern is already seen or not. That's using tries.

1. Add row in trie.
2. If the last node while entering the pattern is leaf node, return false. It's not unique row.
3. If last node is not leaf node, mark it as leaf node and return true.
4. If insert operation return true, print the row.
5. Else, skip printing row.

https://www.geeksforgeeks.org/print-unique-rows/

Method 1 (Simple)
A simple approach is to check each row with all processed rows. Print the first row. Now, starting from the second row, for each row, compare the row with already processed rows. If the row matches with any of the processed rows, don’t print it. If the current row doesn’t match with any row, print it.

Time complexity: O( ROW^2 x COL )
Auxiliary Space: O( 1 )

Code from http://www.geeksforgeeks.org/print-unique-rows/
Link between Matrix and Trie, Use trie to express row in matrix.
Time complexity: O( ROW x COL )
Auxiliary Space: O( ROW x COL )

typedef struct Node

{

    bool isEndOfCol;

    struct Node *child[2]; // Only two children needed for 0 and 1

} Node;

bool insert( Node** root, int (*M)[COL], int row, int col )

{

    // base case

    if ( *root == NULL )

        *root = newNode();

    // Recur if there are more entries in this row

    if ( col < COL )

        return insert ( &( (*root)->child[ M[row][col] ] ), M, row, col+1 );

    else // If all entries of this row are processed

    {

        // unique row found, return 1

        if ( !( (*root)->isEndOfCol ) )

            return (*root)->isEndOfCol = 1;

        // duplicate row found, return 0

        return 0;

    }

}

// The main function that prints all unique rows in a

// given matrix.

void findUniqueRows( int (*M)[COL] )

{

    Node* root = NULL; // create an empty Trie

    int i;

    // Iterate through all rows

    for ( i = 0; i < ROW; ++i )

        // insert row to TRIE

        if ( insert(&root, M, i, 0) )

            // unique row found, print it

            printRow( M, i );

}

Method 4 (Use HashSet data structure)
In this method convert the whole row into a single String and then check it is already present in HashSet or not. If row is present then we will leave it otherwise we will print unique row and add it to HashSet.

    public static void printArray(int arr[][], 

                               int row,int col)

    {

          

        HashSet<String> set = new HashSet<String>();

          

        for(int i = 0; i < row; i++)

        {

            String s = "";

              

            for(int j = 0; j < col; j++) 

                s += String.valueOf(arr[i][j]);

              

            if(!set.contains(s)) {

                set.add(s);

                System.out.println(s);

                  

            }

        }

    }




Method 2 (Use Binary Search Tree)

Find the decimal equivalent of each row and insert it into BST. Each node of the BST will contain two fields, one field for the decimal value, other for row number. Do not insert a node if it is duplicated. Finally, traverse the BST and print the corresponding rows.

Time complexity: O( ROW x COL + ROW x log( ROW ) )
Auxiliary Space: O( ROW )

Or we can use hashtable: get a symbol of each row: sum of a[row][i]*2i
Read full article from Algorithms and Me: Print unique rows in a boolean matrix