Day 15 (Advanced Recursion)

Today, I focused on honing my recursive problem-solving skills by tackling advanced recursion problems. I started by generating all subsets of a set, followed by generating all permutations of a string/array. Then, I explored the "word search in a grid" problem, applying recursion and backtracking to find solutions. I also implemented a recursive solution to the challenging N-Queens problem and solved the "rat in a maze" problem, demonstrating the power of recursion in navigating complex decision trees. These problems strengthened my ability to design recursive solutions for diverse challenges.

Check out my progress in my GitHub repository: github.com/AayJayTee/100-Days-DSA.

Q1. Solve the "generate all subsets of a set" problem using recursion.

#include <iostream>
using namespace std;
#include <vector>

// Function to generate all subsets of the array
void generate_subsets(int arr[], int n, vector<int> sub, int index) {
    if (index == n) {
        for (int i = 0; i < sub.size(); i++) {
            cout << sub[i] << " "; // Print the elements of the subset
        }

        if (sub.size() == 0) {
            cout << "{}"; // Print empty set for subsets with no elements
        }

        cout << endl;
        return; // Return after processing the current subset
    }

    // Exclude the current element and move to the next
    generate_subsets(arr, n, sub, index + 1);

    // Include the current element and move to the next
    sub.push_back(arr[index]);
    generate_subsets(arr, n, sub, index + 1);

    // Backtrack to restore the state of the subset
    sub.pop_back();
}

int main() {
    int n;
    cout << "Enter length of array: ";
    cin >> n; // Input the length of the array
    cout << "Enter elements of the array: ";
    int arr[n];
    for (int i = 0; i < n; i++) {
        cin >> arr[i]; // Input the elements of the array
    }
    vector<int> sub;
    generate_subsets(arr, n, sub, 0); // Generate all subsets
    return 0; // Indicate successful execution
}

This code generates and prints all subsets of a given array using a recursive approach. The function generate_subsets takes the array, its length, a current subset (sub), and the current index as parameters. It uses recursion to explore both possibilities for each element: including it in the current subset or excluding it. When the index reaches the length of the array, the current subset is printed. The base case handles subsets with no elements (empty set). Backtracking is used to undo the inclusion of an element and explore other combinations. The subsets are printed in the order they are generated, with each subset displayed on a new line. The code works by recursively building subsets and outputs all possible subsets, including the empty set.

Q2. Solve the "generate all permutations of a string/array" problem.

#include <iostream>
#include <vector>
using namespace std;

// Function to generate all permutations of the array
void permutation(int nums[], int n, vector<int> &ds, vector<vector<int>> &ans, vector<bool> &freq) {
    if (ds.size() == n) {
        ans.push_back(ds); // Add the current permutation to the result
        return;
    }

    for (int i = 0; i < n; i++) {
        if (!freq[i]) { // If the current element is not already used
            freq[i] = true; // Mark it as used
            ds.push_back(nums[i]); // Include it in the current permutation
            permutation(nums, n, ds, ans, freq); // Recurse for the next element
            ds.pop_back(); // Backtrack: remove the element
            freq[i] = false; // Unmark the element
        }
    }
}

int main() {
    int n;
    cout << "Enter length of array: ";
    cin >> n; // Input size of the array
    cout << "Enter elements of the array: ";
    int arr[n];
    for (int i = 0; i < n; i++) {
        cin >> arr[i]; // Input elements of the array
    }
    vector<int> ds; // Temporary storage for current permutation
    vector<vector<int>> ans; // Storage for all permutations
    vector<bool> freq(n, false); // To track used elements

    permutation(arr, n, ds, ans, freq); // Generate all permutations

    cout << "All permutations are:" << endl;
    for (const auto &permutation : ans) { // Iterate through all permutations
        for (int num : permutation) { // Print each permutation
            cout << num << " ";
        }
        cout << endl;
    }
    return 0;
}

This code generates and prints all permutations of a given array using a backtracking approach. The function permutation takes the array nums, its length n, a temporary vector ds for storing the current permutation, a 2D vector ans for storing all permutations, and a boolean vector freq to track which elements have already been used in the current permutation. The function explores each element of the array, marking it as used when added to the current permutation and recursively building the permutation. Once the permutation reaches the length of the array, it is added to the result. After each recursive call, the element is removed (backtracking), and its usage is unmarked. The main function initializes necessary data structures and calls the permutation function to generate all possible permutations, which are then printed to the console.

Q3. Solve the "word search in a grid" problem using recursion and backtracking.

#include <iostream>
using namespace std;
#include <vector>

// Directions for moving up, down, left, right
vector<vector<int>> directions{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int rows, columns;

// Function to search the word in the grid using backtracking
bool find(vector<vector<char>> &grid, int i, int j, int index, string &str) {
    if (index == str.length()) { // If all characters of the word are found
        return true;
    }
    if (i < 0 || j < 0 || i >= rows || j >= columns || grid[i][j] == '$') { // Out of bounds or already visited
        return false;
    }
    if (grid[i][j] != str[index]) { // If the character doesn't match
        return false;
    }

    // Temporarily mark the cell as visited
    char temp = grid[i][j];
    grid[i][j] = '$';

    // Check all 4 directions (up, down, left, right)
    for (auto &dir : directions) {
        int new_i = i + dir[0];
        int new_j = j + dir[1];

        if (find(grid, new_i, new_j, index + 1, str)) { // Recursively search the next character
            return true;
        }
    }
    grid[i][j] = temp; // Unmark the cell
    return false;
}

// Function to check if the word exists in the grid
bool wordExists(vector<vector<char>> &grid, string str) {
    rows = grid.size(); // Set the number of rows
    columns = grid[0].size(); // Set the number of columns

    // Traverse the grid to find the starting point of the word
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < columns; j++) {
            if (grid[i][j] == str[0] && find(grid, i, j, 0, str)) { // Match the first character and start backtracking
                return true;
            }
        }
    }
    return false; // If the word is not found
}

int main() {
    int m, n;
    cout << "Enter number of rows: ";
    cin >> m; // Input number of rows
    cout << "Enter number of columns: ";
    cin >> n; // Input number of columns

    vector<vector<char>> grid(m, vector<char>(n)); // Initialize grid with m rows and n columns
    cout << "Enter grid elements row by row (characters only):\n";
    for (int i = 0; i < m; i++) { // Input grid elements
        for (int j = 0; j < n; j++) {
            cin >> grid[i][j];
        }
    }

    string word;
    cout << "Enter word to search: ";
    cin >> word; // Input the word to search in the grid

    // Check if the word exists in the grid and output the result
    if (wordExists(grid, word)) {
        cout << "The word '" << word << "' exists in the grid." << endl;
    } else {
        cout << "The word '" << word << "' does not exist in the grid." << endl;
    }

    return 0;
}

This code searches for a given word in a 2D grid of characters using backtracking. It uses a helper function find to recursively check for the presence of the word starting from any character in the grid. The function explores all four directions (up, down, left, right) from a given grid cell and marks visited cells temporarily with a special character ('$'). If the word is found, it returns true; otherwise, it backtracks by unmarking the cell and continuing the search. The wordExists function initializes the grid and iterates through all grid cells, calling the find function whenever the first character of the word is found. If the word can be formed by following the sequence of matching characters, it returns true; otherwise, it returns false. The main function takes input for the grid dimensions, elements, and the word to search for, then prints whether the word exists in the grid.

Q4. Implement a recursive solution for the N-Queens problem.

#include <iostream>
#include <vector>
using namespace std;

// Function to solve the N-Queens problem recursively
void solve(int col, vector<string> &board, vector<vector<string>> &ans, vector<int> &leftRow, vector<int> &upperDiagonal, vector<int> &lowerDiagonal, int n) {
    if (col == n) {
        ans.push_back(board); // Store the current valid board configuration
        return;
    }
    for (int row = 0; row < n; row++) {
        // Check if placing a queen at (row, col) is valid
        if (leftRow[row] == 0 && lowerDiagonal[row + col] == 0 && upperDiagonal[n - 1 + col - row] == 0) {
            board[row][col] = 'Q'; // Place the queen
            leftRow[row] = 1; // Mark the row as occupied
            lowerDiagonal[row + col] = 1; // Mark the lower diagonal as occupied
            upperDiagonal[n - 1 + col - row] = 1; // Mark the upper diagonal as occupied
            solve(col + 1, board, ans, leftRow, upperDiagonal, lowerDiagonal, n); // Recur for the next column
            board[row][col] = 'X'; // Backtrack: remove the queen
            leftRow[row] = 0; // Unmark the row
            lowerDiagonal[row + col] = 0; // Unmark the lower diagonal
            upperDiagonal[n - 1 + col - row] = 0; // Unmark the upper diagonal
        }
    }
}

// Function to initialize and solve the N-Queens problem
vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> ans; // Store all valid board configurations
    vector<string> board(n, string(n, 'X')); // Initialize the board with 'X'
    vector<int> leftRow(n, 0), upperDiagonal(2 * n - 1, 0), lowerDiagonal(2 * n - 1, 0); // Initialize markers
    solve(0, board, ans, leftRow, upperDiagonal, lowerDiagonal, n); // Start solving from column 0
    return ans;
}

// Main function to test the N-Queens problem
int main() {
    int n;
    cout << "Enter the value of n for an n x n board: ";
    cin >> n;

    vector<vector<string>> ans = solveNQueens(n); // Get all valid configurations

    // Print all valid configurations
    for (int i = 0; i < ans.size(); i++) {
        cout << "Arrangement " << i + 1 << ":\n";
        for (const string &row : ans[i]) {
            cout << row << endl;
        }
        cout << endl;
    }
    return 0;
}

This code solves the N-Queens problem using backtracking. The solve function attempts to place queens one by one in each column, checking if the placement is valid by ensuring no two queens attack each other. It uses three arrays—leftRow, upperDiagonal, and lowerDiagonal—to track the availability of rows and diagonals for placing queens. When a valid placement is found, the queen is placed, and the function recursively moves to the next column. If all columns are filled, the current board configuration is added to the result. The function backtracks by removing the queen and unmarking the row and diagonals. The solveNQueens function initializes the board and helper arrays, then calls solve to find all valid solutions. The main function reads the size of the board (n), generates the solutions, and prints each valid arrangement of queens on the board, represented as strings.

Q5. Solve the "rat in a maze" problem using recursion.

#include <iostream>
#include <vector>
using namespace std;

// Function to check if the current cell is valid and safe to move
bool isSafe(vector<vector<int>> &maze, int x, int y, int n) {
    return (x < n && y < n && maze[x][y] == 1);
}

// Recursive function to solve the Rat in a Maze problem
bool ratinMaze(vector<vector<int>> &maze, int x, int y, int n, vector<vector<int>> &solution) {
    if (x == n - 1 && y == n - 1) {
        solution[x][y] = 1; // Mark destination cell
        return true;
    }

    if (isSafe(maze, x, y, n)) {
        solution[x][y] = 1; // Mark the current cell as part of the solution path

        // Move Down
        if (ratinMaze(maze, x + 1, y, n, solution)) {
            return true;
        }

        // Move Right
        if (ratinMaze(maze, x, y + 1, n, solution)) {
            return true;
        }

        solution[x][y] = 0; // Backtrack if neither move leads to a solution
    }
    return false;
}

int main() {
    int n;
    cout << "Enter value of n for nxn maze: ";
    cin >> n;

    // Input maze grid
    vector<vector<int>> maze(n, vector<int>(n));
    cout << "Construct the maze (0 for blocked, 1 for open):" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> maze[i][j];
        }
    }

    // Initialize solution grid with zeros
    vector<vector<int>> solution(n, vector<int>(n, 0));

    // Solve the maze and print the solution
    if (ratinMaze(maze, 0, 0, n, solution)) {
        cout << "Solution exists (1 representing the path its travelled):\n";
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cout << solution[i][j] << " ";
            }
            cout << endl;
        }
    }
    else{
        cout << "No solution exists." << endl;
    }
    return 0;
}

This code solves the "Rat in a Maze" problem using recursion and backtracking. The maze is represented as a 2D grid, where 1 indicates open paths and 0 represents blocked cells. The goal is to find a path from the top-left corner (0,0) to the bottom-right corner (n-1, n-1). The isSafe function checks whether a given cell is within bounds and open. The ratinMaze function recursively explores possible moves, starting from (0, 0), trying to move down or right. If a valid path is found, it marks the current cell as part of the solution and continues to the next cell. If neither direction leads to a solution, it backtracks by unmarking the cell. The solution is stored in a solution grid, where 1 indicates the path taken. The main function reads the maze input, invokes the ratinMaze function, and prints the path if a solution exists, or indicates that no solution is possible.

Today's practice greatly expanded my understanding of recursion and its applications. From generating subsets and permutations to solving intricate puzzles like the N-Queens problem and the rat in a maze, I gained valuable insights into the versatility of recursion and backtracking. These exercises have sharpened my problem-solving abilities and prepared me for even more complex recursive challenges ahead. Looking forward to continuing this journey and diving deeper into advanced algorithmic techniques!