Day 15: 100 Days of DSA

Welcome to Day 15 of my 100 Days of DSA challenge! Today, I solved five problems focused on sliding window technique. Here's a quick look at the questions I tackled and how I approached them 🤖✨ Check out my GitHub repository for all my solutions and progress. Let’s keep learning!

Recursion is a programming technique where a function calls itself to solve smaller sub-problems of a larger problem. It continues breaking down the problem until reaching a base case, which stops the recursion. The results from the smaller sub-problems are then combined to solve the original problem.

How Recursion Helps Solve Advanced Problems:

• Divide and Conquer: Problems like sorting (merge sort, quick sort) use recursion to divide the array into smaller parts and conquer them individually.

• Backtracking: Problems like N-Queens, maze solving, and word search in a grid explore all possible solutions recursively, retracting (backtracking) if a solution fails.

• Dynamic Programming: Recursive solutions with memoization optimize problems like Fibonacci numbers or knapsack by storing already computed results.

• Tree and Graph Traversals: Recursion simplifies traversals like depth-first search (DFS) by exploring paths or subtrees naturally.

• Advanced Problem-Solving: Recursive algorithms solve puzzles (Tower of Hanoi), generate permutations and combinations, and explore game strategies by breaking them into smaller manageable parts.

Recursion is especially powerful when combined with techniques like memoization or backtracking, enabling elegant solutions to complex problems.

I’ll be solving problems on these topics soon, let’s see today’s problems and their code.

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

Code:

// To print all the subsets of a set

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

void subset(int indx, vector<int>ds,int arr[],int size){
    if(indx==size){
        for(auto it:ds){
            cout<<it<<" ";
        }
        cout<<endl;

        if(ds.size()==0){
            cout<<"null";
        }
        return;
    }

    //take the element
    ds.push_back(arr[indx]);
    subset(indx+1,ds,arr,size);
    ds.pop_back();

    //not taking the element
    subset(indx+1,ds,arr,size);

}


int main(){
    cout<<"All the subsets of the given array are:"<<endl;
    int arr[]={3,1,2};
    int size=3;
    vector<int>ds;
    subset(0,ds,arr,size);
}

Output:

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

Code:

// To print all permutaions of an array

#include<iostream>
using namespace std;

void print(int arr[],int size){
    for(int i=0;i<size;i++){
        cout<<arr[i]<<" ";
    }
    cout<<endl;
}
void permutation(int arr[],int size,int indx){
    if(indx==size){
        print(arr,size);
    }

    for(int i=indx;i<size;i++){
        swap(arr[indx],arr[i]);
        permutation(arr,size,indx+1);
        swap(arr[indx],arr[i]);
    }
}

int main(){
    int arr[]={1,2,3};
    int size=3;
    int indx=0;
    permutation(arr,size,indx);
}

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

Code:

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

bool dfs(vector<vector<char>> &board, string &word, int i, int j, int index) {
    if (index == word.size()) return true;
    if (i < 0 || i >= board.size() || j < 0 || j >= board[0].size() || board[i][j] != word[index]) return false;

    char temp = board[i][j];
    board[i][j] = '#';
    bool found = dfs(board, word, i + 1, j, index + 1) ||
                 dfs(board, word, i - 1, j, index + 1) ||
                 dfs(board, word, i, j + 1, index + 1) ||
                 dfs(board, word, i, j - 1, index + 1);
    board[i][j] = temp;
    return found;
}

bool exist(vector<vector<char>> &board, string word) {
    for (int i = 0; i < board.size(); i++) {
        for (int j = 0; j < board[0].size(); j++) {
            if (dfs(board, word, i, j, 0)) return true;
        }
    }
    return false;
}

int main() {
    vector<vector<char>> board = {{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
    string word = "ABCCED";
    cout << (exist(board, word) ? "Word Found" : "Word Not Found") << endl;
    return 0;
}

Output:

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

Code:

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

bool isSafe(vector<string> &board, int row, int col, int n) {
    for (int i = 0; i < row; i++) if (board[i][col] == 'Q') return false;
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) if (board[i][j] == 'Q') return false;
    for (int i = row, j = col; i >= 0 && j < n; i--, j++) if (board[i][j] == 'Q') return false;
    return true;
}

void solve(int row, vector<string> &board, vector<vector<string>> &solutions, int n) {
    if (row == n) {
        solutions.push_back(board);
        return;
    }
    for (int col = 0; col < n; col++) {
        if (isSafe(board, row, col, n)) {
            board[row][col] = 'Q';
            solve(row + 1, board, solutions, n);
            board[row][col] = '.';
        }
    }
}

vector<vector<string>> solveNQueens(int n) {
    vector<vector<string>> solutions;
    vector<string> board(n, string(n, '.'));
    solve(0, board, solutions, n);
    return solutions;
}

int main() {
    int n = 4;
    vector<vector<string>> solutions = solveNQueens(n);
    for (auto &solution : solutions) {
        for (auto &row : solution) cout << row << endl;
        cout << endl;
    }
    return 0;
}

Output:

Two solutions of N Queen

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

Code:

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

bool solveMaze(vector<vector<int>> &maze, int x, int y, vector<vector<int>> &solution) {
    if (x == maze.size() - 1 && y == maze[0].size() - 1) {
        solution[x][y] = 1;
        return true;
    }
    if (x >= 0 && x < maze.size() && y >= 0 && y < maze[0].size() && maze[x][y] == 1) {
        solution[x][y] = 1;
        if (solveMaze(maze, x + 1, y, solution)) return true;
        if (solveMaze(maze, x, y + 1, solution)) return true;
        solution[x][y] = 0;
    }
    return false;
}

void ratInMaze(vector<vector<int>> &maze) {
    vector<vector<int>> solution(maze.size(), vector<int>(maze[0].size(), 0));
    if (solveMaze(maze, 0, 0, solution)) {
        for (auto &row : solution) {
            for (int cell : row) cout << cell << " ";
            cout << endl;
        }
    } else {
        cout << "No Solution" << endl;
    }
}

int main() {
    vector<vector<int>> maze = {{1, 0, 0, 0}, {1, 1, 0, 1}, {0, 1, 0, 0}, {1, 1, 1, 1}};
    ratInMaze(maze);
    return 0;
}

Output:

This is all for today, see ya tomorrow ✨