Welcome to Day 15 of my 100 Days of DSA challenge! Today, I delved into the sliding window technique, solving five problems that emphasized its efficiency in optimizing solutions.
Check out my GitHub repository for all the solutions and progress updates at: 100 Days of DSA
Let’s explore the questions tackled and the approaches used to solve them! 🚀✨
1. Generate All Subsets of a Set
This program generates all subsets of an integer set using recursion. It iteratively includes or excludes each element of the set to form subsets. The base case is reached when all elements are processed, and the current subset is printed.
Code:
#include <iostream>
#include <cmath>
using namespace std;
// Function to generate subsets recursively
void subsets(int set[], int n, string current, int index) {
if (index == n) {
// Base case: print the current subset
cout << "{ " << current << "}" << endl;
return;
}
// Include the current element
subsets(set, n, current + to_string(set[index]) + " ", index + 1);
// Exclude the current element
subsets(set, n, current, index + 1);
}
int main() {
int set[] = {1, 2, 3, 4};
int n = sizeof(set) / sizeof(set[0]);
cout << "The subsets are:" << endl;
subsets(set, n, "", 0);
return 0;
}
Output:
2. Generate All Permutations of a String/Array
This program generates all permutations of a given array using recursion and swapping. It iterates over each element, swapping the current index with others to explore permutations. When the base case is reached (index equals array size), the permutation is printed. Backtracking restores the original array by swapping back after recursive calls.
Code:
#include <iostream>
using namespace std;
// Function to swap two characters
void swap(char &a, char &b) {
char temp = a;
a = b;
b = temp;
}
// Recursive function to generate permutations
void permutations(char arr[], int n, int index) {
if (index == n) {
// Base case: print the permutation
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return;
}
// Generate permutations by swapping and recursing
for (int i = index; i < n; i++) {
swap(arr[index], arr[i]); // Swap current element with the index
permutations(arr, n, index + 1); // Recur for the next index
swap(arr[index], arr[i]); // Backtrack to restore the array
}
}
int main() {
char arr[] = {'A', 'B', 'C'};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "All permutations are:" << endl;
permutations(arr, n, 0);
return 0;
}
Output:
3. Word Search in a Grid
This program uses recursion and backtracking to find if a given word exists in a grid. Starting from each cell that matches the first character of the word, it explores all four directions (up, down, left, right). It marks visited cells temporarily to prevent revisiting and backtracks by restoring the original state after checking each path. If all characters of the word are matched, the word is found.
Code:
#include <iostream>
using namespace std;
// Directions for moving in the grid (right, left, down, up)
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
// Recursive function to perform word search
bool search_word(char grid[][4], int rows, int cols, string word, int x, int y, int index) {
if (index == word.length()) {
// If all characters are found, return true
return true;
}
// Check boundaries and if the current cell matches the character
if (x < 0 || x >= rows || y < 0 || y >= cols || grid[x][y] != word[index]) {
return false;
}
// Temporarily mark the cell as visited
char temp = grid[x][y];
grid[x][y] = '#';
// Explore all 4 directions
for (int d = 0; d < 4; d++) {
int newX = x + dx[d];
int newY = y + dy[d];
if (search_word(grid, rows, cols, word, newX, newY, index + 1)) {
return true;
}
}
// Backtrack by restoring the cell
grid[x][y] = temp;
return false;
}
// Function to find the word in the grid
bool find_word(char grid[][4], int rows, int cols, string word) {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == word[0]) { // Start search if first character matches
if (search_word(grid, rows, cols, word, i, j, 0)) {
return true;
}
}
}
}
return false;
}
int main() {
char grid[3][4] = {
{'A', 'B', 'C', 'E'},
{'S', 'F', 'C', 'S'},
{'A', 'D', 'E', 'E'}
};
string word = "BCE";
if (find_word(grid, 3, 4, word)) {
cout << "Word found in the grid!" << endl;
} else {
cout << "Word not found in the grid!" << endl;
}
return 0;
}
Output:
4. N-Queens Problem
This program solves the N-Queens problem by placing queens on an N×N chessboard using recursion and backtracking. It checks if a position is safe for a queen by ensuring no conflicts in the column, upper-left diagonal, or upper-right diagonal. Queens are placed row by row, and if a placement doesn't lead to a solution, the program backtracks by removing the queen and trying the next column.
Code:
#include <iostream>
using namespace std;
#define N 4 // Define the size of the chessboard
// Function to print the board
void print_board(int board[N][N]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << (board[i][j] ? "Q " : ". ");
}
cout << endl;
}
cout << endl;
}
// Function to check if it's safe to place a queen at board[row][col]
bool is_safe(int board[N][N], int row, int col) {
// Check this column on upper rows
for (int i = 0; i < row; i++) {
if (board[i][col]) {
return false;
}
}
// Check the upper left diagonal
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
if (board[i][j]) {
return false;
}
}
// Check the upper right diagonal
for (int i = row, j = col; i >= 0 && j < N; i--, j++) {
if (board[i][j]) {
return false;
}
}
return true;
}
// Recursive function to solve the N-Queens problem
bool n_queens(int board[N][N], int row) {
if (row >= N) {
// All queens placed successfully
print_board(board);
return true;
}
bool result = false;
for (int col = 0; col < N; col++) {
if (is_safe(board, row, col)) {
// Place the queen
board[row][col] = 1;
// Recur for the next row
result = n_queens(board, row + 1) || result;
// Backtrack and remove the queen
board[row][col] = 0;
}
}
return result;
}
int main() {
int board[N][N] = {0}; // Initialize the board with all zeros
if (!n_queens(board, 0)) {
cout << "No solution exists for " << N << " queens." << endl;
}
return 0;
}
Output:
5. Rat in a Maze Problem
This program solves the "Rat in a Maze" problem using recursion and backtracking. It starts by attempting to move the rat from the top-left corner of the maze to the bottom-right corner. At each step, it checks if the current position is valid (open path) and recursively tries to move right and down. If a valid path is found, it marks the path in a solution matrix. If no valid path is found from a position, the program backtracks by unmarking the cell and trying other options. The solution, if found, is displayed as a matrix showing the path the rat took.
Code:
#include <iostream>
using namespace std;
#define N 4 // Define the size of the maze (N x N)
// Function to print the solution path
void print_solution(int sol[N][N]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << sol[i][j] << " ";
}
cout << endl;
}
}
// Function to check if it's safe to move to grid[x][y]
bool is_safe(int maze[N][N], int x, int y) {
// Check if (x, y) is within the grid and is a valid path (1)
return (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1);
}
// Recursive function to solve the Maze problem
bool solve_maze(int maze[N][N], int x, int y, int sol[N][N]) {
// If the rat reaches the bottom-right corner, the solution is found
if (x == N - 1 && y == N - 1) {
sol[x][y] = 1;
return true;
}
// Check if the current position is safe
if (is_safe(maze, x, y)) {
// Mark the current cell as part of the solution path
sol[x][y] = 1;
// Move to the right (x, y + 1)
if (solve_maze(maze, x, y + 1, sol)) {
return true;
}
// Move down (x + 1, y)
if (solve_maze(maze, x + 1, y, sol)) {
return true;
}
// If none of the above moves work, backtrack
sol[x][y] = 0;
return false;
}
return false; // If the position is not safe, return false
}
int main() {
// Define a sample maze where 1 represents a valid path and 0 is blocked
int maze[N][N] = {
{1, 0, 1, 0},
{1, 1, 1, 1},
{0, 1, 0, 0},
{1, 1, 1, 1}
};
int sol[N][N] = {0};
if (solve_maze(maze, 0, 0, sol)) {
cout << "Solution Path:" << endl;
print_solution(sol);
} else {
cout << "No solution exists." << endl;
}
return 0;
}
Output:
Day 15 showcased the power of the recursion in optimizing problem-solving for a variety of challenges. By using this approach, I was able to efficiently handle tasks involving subarrays and strings, proving its effectiveness in reducing time complexity. It was a great day of learning, and I'm excited to dive into more complex problems tomorrow! 🚀