Coding Interview Questions Interview Questions and Answers

New 60 Backtracking Interview Question

Deepak Vishwakarma July 28, 2023Last Updated: July 28, 2023

0 2 42 minutes read

Table of Contents

Introduction

Backtracking is a powerful algorithmic technique used to solve problems by exploring all possible solutions. In an interview, you may encounter backtracking questions that require you to find the best solution through a systematic approach. The idea behind backtracking is to build a solution incrementally and backtrack when a dead-end is reached. By exploring different paths and making informed choices, backtracking efficiently solves problems like Sudoku, N-Queens, or solving a maze. These questions assess your problem-solving skills, ability to handle recursion, and logical thinking. Understanding the basics of backtracking and practicing related problems can significantly help you tackle such interview questions effectively.

Questions

1. What is Backtracking?

Backtracking is an algorithmic technique for solving problems by trying out different possibilities and undoing the choices that don’t lead to a valid solution. It explores all possible options but prunes the search space whenever it identifies that a specific choice will not lead to the correct answer.

C++ Code Example – Backtracking for finding all subsets of a set:

C++

#include <iostream>
#include <vector>

using namespace std;

void backtrack(vector<int>& nums, int start, vector<int>& subset, vector<vector<int>>& subsets) {
    subsets.push_back(subset);

    for (int i = start; i < nums.size(); ++i) {
        subset.push_back(nums[i]);
        backtrack(nums, i + 1, subset, subsets);
        subset.pop_back();
    }
}

vector<vector<int>> findAllSubsets(vector<int>& nums) {
    vector<vector<int>> subsets;
    vector<int> subset;
    backtrack(nums, 0, subset, subsets);
    return subsets;
}

int main() {
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> subsets = findAllSubsets(nums);

    for (const auto& subset : subsets) {
        for (int num : subset) {
            cout << num << " ";
        }
        cout << endl;
    }

    return 0;
}

2. What are the common problems solved by Backtracking?

Finding all permutations or combinations of a set of elements.
Sudoku solving.
N-Queens problem.
Knight’s tour problem.
Rat in a Maze problem.
Subset or subset sum problem.
Graph problems like Hamiltonian Cycle, Graph Coloring, etc.
Crossword puzzles and word games.

3. What are some applications of Backtracking?

Combinatorial optimization problems.
Solving constraint satisfaction problems.
Solving puzzles and games.
Generating all possible configurations for a problem.
Cryptography, for breaking codes and ciphers.

4. What is the difference between Backtracking and Recursion?

Backtracking	Recursion
Backtracking is a specific algorithmic technique.	Recursion is a general programming concept.
It involves exploring all possible solutions.	It may involve exploring all possible states or paths.
Backtracking typically involves undoing choices.	Recursion doesn’t necessarily involve undoing choices.
Primarily used for solving optimization problems.	Used for a wide range of problems and program flow.
It can be more efficient when pruning options early.	It may explore unnecessary paths without pruning.

5. How does Backtracking work?

Backtracking works by exploring all possible choices to find a solution. If a choice leads to an incorrect or invalid solution, the algorithm backtracks and tries a different option.

Example – Solving the N-Queens problem using backtracking:

C++

#include <iostream>
#include <vector>

using namespace std;

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

bool solveNQueensUtil(vector<vector<int>>& board, int row, int N) {
    if (row == N) {
        return true;
    }

    for (int col = 0; col < N; ++col) {
        if (isSafe(board, row, col, N)) {
            board[row][col] = 1;

            if (solveNQueensUtil(board, row + 1, N)) {
                return true;
            }

            board[row][col] = 0; // Backtrack if the placement is invalid
        }
    }
    return false;
}

vector<vector<int>> solveNQueens(int N) {
    vector<vector<int>> board(N, vector<int>(N, 0));
    vector<vector<int>> result;

    if (solveNQueensUtil(board, 0, N)) {
        result = board;
    }

    return result;
}

int main() {
    int N = 4;
    vector<vector<int>> solutions = solveNQueens(N);

    for (const auto& row : solutions) {
        for (int cell : row) {
            cout << (cell == 1 ? "Q " : ". ");
        }
        cout << endl;
    }

    return 0;
}

6. What is the time complexity of a backtracking algorithm?

The time complexity of a backtracking algorithm depends on the problem and the number of valid solutions it needs to explore. In the worst case, a backtracking algorithm can have an exponential time complexity, O(b^d), where b is the branching factor (number of choices at each step) and d is the depth of the state space tree. However, through pruning and optimizations, the actual time taken may be much less than the worst-case scenario.

7. What is the concept of the state-space tree in Backtracking?

The state-space tree in backtracking represents all the possible states or choices that can be made to reach a solution for a specific problem. Each node in the tree represents a specific state, and the branches represent different choices that can be made from that state.

Example – Generating all possible subsets using backtracking:

C++

#include <iostream>
#include <vector>

using namespace std;

void backtrack(vector<int>& nums, int start, vector<int>& subset, vector<vector<int>>& subsets) {
    subsets.push_back(subset);

    for (int i = start; i < nums.size(); ++i) {
        subset.push_back(nums[i]);
        backtrack(nums, i + 1, subset, subsets);
        subset.pop_back();
    }
}

vector<vector<int>> findAllSubsets(vector<int>& nums) {
    vector<vector<int>> subsets;
    vector<int> subset;
    backtrack(nums, 0, subset, subsets);
    return subsets;
}

int main() {
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> subsets = findAllSubsets(nums);


    for(const auto& subset : subsets) {
        for (int num : subset) {
            cout << num << " ";
        }
        cout << endl;
    }

    return 0;
}

8. Explain how Backtracking can be used to solve Sudoku puzzles?

Backtracking can be used to solve Sudoku puzzles by trying out different numbers in empty cells and recursively exploring the possible solutions. Whenever an invalid choice is made, the algorithm backtracks and tries a different number until a valid solution is found.

Example – Solving a Sudoku puzzle using backtracking:

C++

#include <iostream>
#include <vector>

using namespace std;

const int N = 9;

bool isSafe(vector<vector<int>>& board, int row, int col, int num) {
    // Check if 'num' is not present in current row, column, and 3x3 grid
    for (int i = 0; i < N; ++i) {
        if (board[row][i] == num || board[i][col] == num || board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == num) {
            return false;
        }
    }
    return true;
}

bool solveSudokuUtil(vector<vector<int>>& board) {
    int row, col;
    if (!findEmptyCell(board, row, col)) {
        return true; // All cells are filled, solution found!
    }

    for (int num = 1; num <= 9; ++num) {
        if (isSafe(board, row, col, num)) {
            board[row][col] = num;

            if (solveSudokuUtil(board)) {
                return true;
            }

            board[row][col] = 0; // Backtrack if the placement is invalid
        }
    }
    return false;
}

bool findEmptyCell(vector<vector<int>>& board, int& row, int& col) {
    for (row = 0; row < N; ++row) {
        for (col = 0; col < N; ++col) {
            if (board[row][col] == 0) {
                return true;
            }
        }
    }
    return false;
}

void solveSudoku(vector<vector<int>>& board) {
    solveSudokuUtil(board);
}

int main() {
    vector<vector<int>> board = {
        {5, 3, 0, 0, 7, 0, 0, 0, 0},
        {6, 0, 0, 1, 9, 5, 0, 0, 0},
        {0, 9, 8, 0, 0, 0, 0, 6, 0},
        {8, 0, 0, 0, 6, 0, 0, 0, 3},
        {4, 0, 0, 8, 0, 3, 0, 0, 1},
        {7, 0, 0, 0, 2, 0, 0, 0, 6},
        {0, 6, 0, 0, 0, 0, 2, 8, 0},
        {0, 0, 0, 4, 1, 9, 0, 0, 5},
        {0, 0, 0, 0, 8, 0, 0, 7, 9}
    };

    solveSudoku(board);

    // Print the solved Sudoku board
    for (const auto& row : board) {
        for (int num : row) {
            cout << num << " ";
        }
        cout << endl;
    }

    return 0;
}

9. What are the advantages and disadvantages of Backtracking?

Advantages:

Can efficiently solve optimization problems with a large search space.
Helps to find all possible solutions to a problem.
Allows pruning to avoid unnecessary exploration of certain paths.

Disadvantages:

In the worst case, the time complexity can be exponential.
It may explore a large number of possibilities, leading to slow execution.
Implementation can be complex and require careful handling of states and choices.

10. How can Backtracking be used for combinatorial problems?

Backtracking can be used to find all possible combinations or permutations of a set of elements. By trying out different orders or selections, we can generate all valid combinations.

Example – Generating all possible permutations using backtracking:

C++

#include <iostream>
#include <vector>

using namespace std;

void backtrack(vector<int>& nums, vector<bool>& used, vector<int>& permutation, vector<vector<int>>& permutations) {
    if (permutation.size() == nums.size()) {
        permutations.push_back(permutation);
        return;
    }

    for (int i = 0; i < nums.size(); ++i) {
        if (!used[i]) {
            used[i] = true;
            permutation.push_back(nums[i]);
            backtrack(nums, used, permutation, permutations);
            permutation.pop_back();
            used[i] = false;
        }
    }
}

vector<vector<int>> findPermutations(vector<int>& nums) {
    vector<vector<int>> permutations;
    vector<int> permutation;
    vector<bool> used(nums.size(), false);
    backtrack(nums, used, permutation, permutations);
    return permutations;
}

int main() {
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> permutations = findPermutations(nums);

    for (const auto& permutation : permutations) {
        for (int num : permutation) {
            cout << num << " ";
        }
        cout << endl;
    }

    return 0;
}

11. What is the difference between Backtracking and Dynamic Programming?

Backtracking	Dynamic Programming
Algorithmic technique for exhaustive search.	Algorithmic technique for optimization problems.
Explores all possible solutions.	Solves subproblems and stores solutions in a table.
Usually involves a depth-first search.	Doesn’t necessarily follow a specific search strategy.
Pruning can be used to reduce search space.	Memoization or tabulation to avoid redundant calculations.
Exponential time complexity in the worst case.	Polynomial time complexity due to reusing subproblems.

12. Explain how the Knight’s tour problem can be solved using Backtracking?

The Knight’s tour problem is about finding a sequence of moves for a knight on a chessboard such that the knight visits every square exactly once.

To solve the Knight’s tour problem using backtracking:

Start with an empty chessboard and place the knight on any square.
Try all possible moves from the current position.
If a move leads to a valid square not yet visited, mark that square and move the knight there.
Repeat steps 2 and 3 until all squares are visited, or there are no more valid moves.
If all squares are visited, the problem is solved. Otherwise, backtrack and try other moves.

Diagram (N = 5, the knight’s tour starts at position (0, 0)):

1   10   21    4   19
22    5   20   11    2
9   14    3   18   25
16   23    8   13    6
7   12   15   24   17

13. What is the role of the decision space tree in Backtracking?

The decision space tree in backtracking represents all the possible decisions or choices that can be made at each step while solving a problem. Each node in the tree corresponds to a specific decision or choice, and the branches represent different options available for that decision.

Diagram (Decision space tree for finding subsets of {1, 2, 3}):

Level 0: [] (Empty set)
        |
Level 1: [1]
        / \
Level 2: [1, 2]   [1, 3]
         /       \
Level 3: [1, 2, 3]

In this example, the decision space tree represents the process of finding all subsets of the set {1, 2, 3} using backtracking. At each level, the algorithm makes a decision to either include or exclude an element from the set, exploring all possible combinations to find all subsets.

14. How can we prevent duplicate solutions in Backtracking?

To prevent duplicate solutions in backtracking, we can use the following techniques:

Use proper ordering of choices: Arrange the choices in a way that avoids duplicates. For example, sorting the input array can help ensure that duplicate elements are considered in a consistent order.
Use a data structure to track used elements: Maintain a data structure like a set or a bitmask to keep track of used elements during exploration. Before making a decision, check if the element has already been used, and if so, skip that choice.
Apply constraints during exploration: Introduce constraints or conditions to ensure that only distinct solutions are explored. For example, in a Sudoku puzzle, you can check the constraints of rows, columns, and 3×3 subgrids to prevent duplicate numbers in the same row, column, or subgrid.

15. Explain the concept of “pruning” in Backtracking?

Pruning in backtracking refers to the process of avoiding the exploration of certain paths that are guaranteed not to lead to a valid solution. When we identify that a specific choice will not lead to the correct answer, we stop further exploration of that path and backtrack to try other options.

For example, in the N-Queens problem, if we find that placing a queen at a specific row and column will lead to conflicts with other queens, there is no need to explore further down that path. We can immediately backtrack and try a different position for that queen.

16. What are some ways to optimize a backtracking algorithm?

To optimize a backtracking algorithm, we can use the following techniques:

Pruning: As discussed earlier, prune unnecessary paths that won’t lead to a valid solution.
Smart ordering of choices: Choose the order of options to explore carefully to increase the chances of reaching a valid solution quickly.
Memoization: In dynamic programming with backtracking, store the results of subproblems and reuse them to avoid redundant calculations.
Use data structures efficiently: Utilize appropriate data structures like sets, bitmasks, or arrays to track used elements and make decisions efficiently.
Avoid deep copying: When updating the state during exploration, try to use references or pointers instead of deep copying, as copying large data structures can be time-consuming.
Early exit conditions: If the problem allows it, use early exit conditions to stop exploring further once a valid solution is found. This can save unnecessary exploration.

17. How is Backtracking used in the N-queens problem?

Backtracking is used to solve the N-Queens problem by placing N queens on an N×N chessboard in such a way that no two queens threaten each other.

C++ Code Example for N-Queens problem:

C++

#include <iostream>
#include <vector>

using namespace std;

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

bool solveNQueensUtil(vector<vector<int>>& board, int row, int N) {
    if (row == N) {
        return true;
    }

    for (int col = 0; col < N; ++col) {
        if (isSafe(board, row, col, N)) {
            board[row][col] = 1;

            if (solveNQueensUtil(board, row + 1, N)) {
                return true;
            }

            board[row][col] = 0; // Backtrack if the placement is invalid
        }
    }
    return false;
}

vector<vector<int>> solveNQueens(int N) {
    vector<vector<int>> board(N, vector<int>(N, 0));
    vector<vector<int>> result;

    if (solveNQueensUtil(board, 0, N)) {
        result = board;
    }

    return result;
}

int main() {
    int N = 4;
    vector<vector<int>> solutions = solveNQueens(N);

    for (const auto& row : solutions) {
        for (int cell : row) {
            cout << (cell == 1 ? "Q " : ". ");
        }
        cout << endl;
    }

    return 0;
}

18. What are bounding functions in Backtracking?

Bounding functions in backtracking are used to determine whether further exploration of a specific path is worthwhile or not. These functions help in making decisions to prune certain branches of the state-space tree when it’s guaranteed that they won’t lead to a valid solution.

Bounding functions are typically used in optimization problems to discard unpromising paths early and reduce the search space. By bounding the search, backtracking can focus on areas of the solution space more likely to yield optimal results.

For example, in the N-Queens problem, a bounding function can check if it’s possible to place the remaining queens in a way that guarantees a valid solution. If not, it prunes that particular branch of the state-space tree.

19. Explain how Backtracking can be used to solve the Rat in a Maze problem?

The Rat in a Maze problem is about finding a path for a rat from the top-left corner to the bottom-right corner in a maze, moving only right or down, and avoiding obstacles.

C++ Code Example for the Rat in a Maze problem:

C++

<code>#include <iostream>
#include <vector>

using namespace std;

bool isSafe(vector<vector<int>>& maze, int x, int y, int N) {
    return (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1);
}

bool solveMazeUtil(vector<vector<int>>& maze, int x, int y, vector<vector<int>>& path, int N) {
    if (x == N - 1 && y == N - 1) {
        path[x][y] = 1;
        return true;
    }

    if (isSafe(maze, x, y, N)) {
        path[x][y] = 1;

        if (solveMazeUtil(maze, x + 1, y, path, N))
            return true;

        if (solveMazeUtil(maze, x, y + 1, path, N))
            return true;

        path[x][y] = 0; // Backtrack if both down and right moves are invalid
        return false;
    }

    return false;
}

vector<vector<int>> solveMaze(vector<vector<int>>& maze) {
    int N = maze.size();
    vector<vector<int>> path(N, vector<int>(N, 0));

    if (solveMazeUtil(maze, 0, 0, path, N)) {
        return path;
    }

    return vector<vector<int>>();
}

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

    vector<vector<int>> path = solveMaze(maze);

    if (path.empty()) {
        cout << "No path found!" << endl;
    } else {
        for (const auto& row : path) {
            for (int cell : row) {
                cout << (cell == 1 ? "P " : "X ");
            }
            cout << endl;
        }
    }

    return 0;
}</code>

20. How can we use Backtracking to generate all possible permutations of a sequence?

To generate all possible permutations of a sequence using backtracking, we can follow these steps:

Start with an empty permutation.
At each step, choose an element from the remaining unused elements in the sequence.
Add the chosen element to the permutation and mark it as used.
Recur for the remaining elements and explore all possible choices.
Backtrack by undoing the choice and marking the element as unused before trying the next option.

C++ Code Example for generating all possible permutations:

C++

#include <iostream>
#include <vector>

using namespace std;

void backtrack(vector<int>& nums, vector<bool>& used, vector<int>& permutation, vector<vector<int>>& permutations) {
    if (permutation.size() == nums.size()) {
        permutations.push_back(permutation);
        return;
    }

    for (int i = 0; i < nums.size(); ++i) {
        if (!used[i]) {
            used[i] = true;
            permutation.push_back(nums[i]);
            backtrack(nums, used, permutation, permutations);
            permutation.pop_back();
            used[i] = false;
        }
    }
}

vector<vector<int>> findPermutations(vector<int>& nums) {
    vector<vector<int>> permutations;
    vector<int> permutation;
    vector<bool> used(nums.size(), false);
    backtrack(nums, used, permutation, permutations);
    return permutations;
}

int main() {
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> permutations = findPermutations(nums);

    for (const auto& permutation : permutations) {
        for (int num : permutation) {
            cout << num << " ";
        }
        cout << endl;
    }

    return 0;
}

This code will output all possible permutations of the input sequence {1, 2, 3}:

C++

Coding Questions

1. Generate all the binary strings of N bits.

C++

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

void generateBinaryStrings(int N, string curr) {
    if (N == 0) {
        cout << curr << endl;
        return;
    }

    generateBinaryStrings(N - 1, curr + "0");
    generateBinaryStrings(N - 1, curr + "1");
}

int main() {
    int N;
    cout << "Enter the number of bits: ";
    cin >> N;

    generateBinaryStrings(N, "");

    return 0;
}

2. Print all the permutations of a given string.

C++

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

void generatePermutations(string str, int start, int end) {
    if (start == end) {
        cout << str << endl;
        return;
    }

    for (int i = start; i <= end; i++) {
        swap(str[start], str[i]);
        generatePermutations(str, start + 1, end);
        swap(str[start], str[i]);
    }
}

int main() {
    string str;
    cout << "Enter the string: ";
    cin >> str;

    generatePermutations(str, 0, str.length() - 1);

    return 0;
}

3. Solve the Rat in a Maze problem.

C++

#include <iostream>
using namespace std;

#define N 4

bool solveMazeUtil(int maze[N][N], int x, int y, int sol[N][N]) {
    if (x == N - 1 && y == N - 1) {
        sol[x][y] = 1;
        return true;
    }

    if (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1) {
        sol[x][y] = 1;

        if (solveMazeUtil(maze, x + 1, y, sol))
            return true;

        if (solveMazeUtil(maze, x, y + 1, sol))
            return true;

        sol[x][y] = 0;
    }

    return false;
}

void solveMaze(int maze[N][N]) {
    int sol[N][N] = {0};

    if (!solveMazeUtil(maze, 0, 0, sol))
        cout << "No solution exists!" << endl;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << sol[i][j] << " ";
        }
        cout << endl;
    }
}

int main() {
    int maze[N][N] = {{1, 0, 0, 0},
                      {1, 1, 0, 1},
                      {0, 1, 0, 0},
                      {1, 1, 1, 1}};

    solveMaze(maze);

    return 0;
}

4. Solve the N-Queens problem.

C++

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

bool isSafe(vector<vector<int>>& board, int row, int col) {
    int N = board.size();

    for (int i = 0; i < row; i++) {
        if (board[i][col] == 1)
            return false;
    }

    for (int i = row

, j = col; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 1)
            return false;
    }

    for (int i = row, j = col; i >= 0 && j < N; i--, j++) {
        if (board[i][j] == 1)
            return false;
    }

    return true;
}

bool solveNQueensUtil(vector<vector<int>>& board, int row) {
    int N = board.size();

    if (row == N) {
        // Print the board configuration
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cout << board[i][j] << " ";
            }
            cout << endl;
        }
        cout << endl;

        return true;
    }

    bool res = false;

    for (int col = 0; col < N; col++) {
        if (isSafe(board, row, col)) {
            board[row][col] = 1;

            res = solveNQueensUtil(board, row + 1) || res;

            board[row][col] = 0;
        }
    }

    return res;
}

void solveNQueens(int N) {
    vector<vector<int>> board(N, vector<int>(N, 0));

    if (!solveNQueensUtil(board, 0))
        cout << "No solution exists!" << endl;
}

int main() {
    int N;
    cout << "Enter the number of queens: ";
    cin >> N;

    solveNQueens(N);

    return 0;
}

5. Generate all possible balanced parentheses.

C++

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

void generateBalancedParentheses(int n, int open, int close, string curr) {
    if (open == n && close == n) {
        cout << curr << endl;
        return;
    }

    if (open < n)
        generateBalancedParentheses(n, open + 1, close, curr + "(");

    if (close < open)
        generateBalancedParentheses(n, open, close + 1, curr + ")");
}

int main() {
    int n;
    cout << "Enter the number of parentheses pairs: ";
    cin >> n;

    generateBalancedParentheses(n, 0, 0, "");

    return 0;
}

6. Print all subsets of a given set.

C++

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

void printSubsets(vector<int>& nums, vector<int>& subset, int index) {
    if (index == nums.size()) {
        cout << "{ ";
        for (int num : subset) {
            cout << num << " ";
        }
        cout << "}" << endl;
        return;
    }

    subset.push_back(nums[index]);
    printSubsets(nums, subset, index + 1);
    subset.pop_back();
    printSubsets(nums, subset, index + 1);
}

void generateSubsets(vector<int>& nums) {
    vector<int> subset;
    printSubsets(nums, subset, 0);
}

int main() {
    vector<int> nums = {1, 2, 3};

    generateSubsets(nums);

    return 0;
}

7. Generate all the permutations of a given sequence.

C++

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

void generatePermutations(vector<int>& nums, int start,

 vector<vector<int>>& result) {
    if (start == nums.size()) {
        result.push_back(nums);
        return;
    }

    for (int i = start; i < nums.size(); i++) {
        swap(nums[start], nums[i]);
        generatePermutations(nums, start + 1, result);
        swap(nums[start], nums[i]);
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> result;
    generatePermutations(nums, 0, result);
    return result;
}

int main() {
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> result = permute(nums);

    for (vector<int>& permutation : result) {
        cout << "{ ";
        for (int num : permutation) {
            cout << num << " ";
        }
        cout << "}" << endl;
    }

    return 0;
}

8. Find all possible combinations of r elements in a given array of size n.

C++

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

void generateCombinations(vector<int>& nums, int r, int start, vector<int>& current, vector<vector<int>>& result) {
    if (current.size() == r) {
        result.push_back(current);
        return;
    }

    for (int i = start; i < nums.size(); i++) {
        current.push_back(nums[i]);
        generateCombinations(nums, r, i + 1, current, result);
        current.pop_back();
    }
}

vector<vector<int>> combine(vector<int>& nums, int r) {
    vector<vector<int>> result;
    vector<int> current;
    generateCombinations(nums, r, 0, current, result);
    return result;
}

int main() {
    vector<int> nums = {1, 2, 3, 4};
    int r = 3;
    vector<vector<int>> result = combine(nums, r);

    for (vector<int>& combination : result) {
        cout << "{ ";
        for (int num : combination) {
            cout << num << " ";
        }
        cout << "}" << endl;
    }

    return 0;
}

9. Solve the Knight’s Tour problem.

C++

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

#define N 8

bool isSafe(int x, int y, vector<vector<int>>& sol) {
    return (x >= 0 && x < N && y >= 0 && y < N && sol[x][y] == -1);
}

void printSolution(vector<vector<int>>& sol) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << sol[i][j] << " ";
        }
        cout << endl;
    }
}

bool solveKnightTourUtil(int x, int y, int move, vector<vector<int>>& sol, vector<int>& xMove, vector<int>& yMove) {
    if (move == N * N) {
        printSolution(sol);
        return true;
    }

    for (int k = 0; k < 8; k++) {
        int nextX = x + xMove[k];
        int nextY = y + yMove[k];

        if (isSafe(nextX, nextY, sol)) {
            sol[nextX][nextY] = move;
            if (solveKnightTourUtil(nextX, nextY, move + 1, sol, xMove, yMove))
                return true;
            sol[nextX][nextY] =

 -1;
        }
    }

    return false;
}

void solveKnightTour() {
    vector<vector<int>> sol(N, vector<int>(N, -1));
    vector<int> xMove = {2, 1, -1, -2, -2, -1, 1, 2};
    vector<int> yMove = {1, 2, 2, 1, -1, -2, -2, -1};

    sol[0][0] = 0;
    if (!solveKnightTourUtil(0, 0, 1, sol, xMove, yMove))
        cout << "No solution exists!" << endl;
}

int main() {
    solveKnightTour();

    return 0;
}

10. Find the longest possible route in a matrix.

C++

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

#define N 3
#define M 3

int findLongestPathUtil(vector<vector<int>>& matrix, vector<vector<int>>& dp, int i, int j) {
    if (i < 0 || i >= N || j < 0 || j >= M)
        return 0;

    if (dp[i][j] != -1)
        return dp[i][j];

    int up = (i > 0 && matrix[i][j] + 1 == matrix[i - 1][j]) ? (1 + findLongestPathUtil(matrix, dp, i - 1, j)) : 0;
    int down = (i < N - 1 && matrix[i][j] + 1 == matrix[i + 1][j]) ? (1 + findLongestPathUtil(matrix, dp, i + 1, j)) : 0;
    int left = (j > 0 && matrix[i][j] + 1 == matrix[i][j - 1]) ? (1 + findLongestPathUtil(matrix, dp, i, j - 1)) : 0;
    int right = (j < M - 1 && matrix[i][j] + 1 == matrix[i][j + 1]) ? (1 + findLongestPathUtil(matrix, dp, i, j + 1)) : 0;

    int maxLength = max(up, max(down, max(left, right)));
    dp[i][j] = maxLength;

    return maxLength;
}

int findLongestPath(vector<vector<int>>& matrix) {
    vector<vector<int>> dp(N, vector<int>(M, -1));

    int maxLength = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (dp[i][j] == -1)
                findLongestPathUtil(matrix, dp, i, j);
            maxLength = max(maxLength, dp[i][j]);
        }
    }

    return maxLength;
}

int main() {
    vector<vector<int>> matrix = {{1, 2, 9},
                                  {5, 3, 8},
                                  {4, 6, 7}};

    int maxLength = findLongestPath(matrix);
    cout << "The longest possible route in the matrix: " << maxLength << endl;

    return 0;
}

11. Find path from corner cell to middle cell in a maze.

C++

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

bool isValidCell(int x, int y, int rows, int cols) {
    return (x >= 0 && x < rows && y >= 0 && y < cols);
}

bool findPathInMaze(vector<vector<int>>& maze, int x, int y, int rows, int cols, vector<pair<int, int>>& path) {
    if (!isValidCell(x, y, rows, cols) || maze[x][y] == 0)
        return false;

    path.push_back(make_pair(x, y));

    if (x == rows / 2 && y == cols / 2)
        return true;

    bool found = findPathInMaze(maze, x + 1, y, rows, cols, path) || findPathInMaze(maze, x, y + 1, rows, cols, path);

    if (!found)
        path.pop_back();

    return found;
}

void printPath(vector<pair<int, int>>& path) {
    for (auto p : path) {
        cout << "(" << p.first << ", " << p.second << ") ";
    }
    cout << endl;
}

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

    int rows = maze.size();
    int cols = maze[0].size();

    vector<pair<int, int>> path;

    bool foundPath = findPathInMaze(maze, 0, 0, rows, cols, path);

    if (foundPath) {
        cout << "Path from corner cell to middle cell in the maze:" << endl;
        printPath(path);
    } else {
        cout << "No path found!" << endl;
    }

    return 0;
}

12. Print all possible paths from the first row to the last row in a 2D array.

C++

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

void printPaths(vector<vector<int>>& matrix, vector<int>& path, int row, int col) {
    int rows = matrix.size();
    int cols = matrix[0].size();

    path.push_back(matrix[row][col]);

    if (row == rows - 1) {
        for (int num : path)
            cout << num << " ";
        cout << endl;
    } else {
        if (col > 0)
            printPaths(matrix, path, row + 1, col - 1);
        printPaths(matrix, path, row + 1, col);
        if (col < cols - 1)
            printPaths(matrix, path, row + 1, col + 1);
    }

    path.pop_back();
}

int main() {
    vector<vector<int>> matrix = {{1, 2, 3},
                                  {4, 5, 6},
                                  {7, 8, 9}};

    int rows = matrix.size();
    int cols = matrix[0].size();

    vector<int> path;

    cout << "All possible paths from the first row to the last row:" << endl;
    for (

int i = 0; i < cols; i++) {
        printPaths(matrix, path, 0, i);
    }

    return 0;
}

13. Solve the Word Search problem.

C++

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

bool searchWord(vector<vector<char>>& board, string& word, int row, int col, int index) {
    if (index == word.length())
        return true;

    int rows = board.size();
    int cols = board[0].size();

    if (row < 0 || row >= rows || col < 0 || col >= cols || board[row][col] != word[index])
        return false;

    char temp = board[row][col];
    board[row][col] = '#';  // Mark the cell as visited

    bool found = searchWord(board, word, row + 1, col, index + 1) ||
                 searchWord(board, word, row - 1, col, index + 1) ||
                 searchWord(board, word, row, col + 1, index + 1) ||
                 searchWord(board, word, row, col - 1, index + 1);

    board[row][col] = temp;  // Reset the cell

    return found;
}

bool exist(vector<vector<char>>& board, string word) {
    int rows = board.size();
    int cols = board[0].size();

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (board[i][j] == word[0] && searchWord(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";

    if (exist(board, word))
        cout << "The word '" << word << "' exists in the board." << endl;
    else
        cout << "The word '" << word << "' does not exist in the board." << endl;

    return 0;
}

14. Solve the Sudoku puzzle.

C++

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

#define UNASSIGNED 0
#define N 9

bool isSafe(vector<vector<int>>& board, int row, int col, int num) {
    for (int i = 0; i < N; i++) {
        if (board[row][i] == num)
            return false;

        if (board[i][col] == num)
            return false;

        if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == num)
            return false;
    }

    return true;
}

bool solveSudokuUtil(vector<vector<int>>& board, int row, int col) {
    if (row == N - 1 && col == N)
        return true;

    if (col == N) {
        row++;
        col = 0;
    }

    if (board[row][col] != UNASSIGNED)
        return solveSudokuUtil(board, row, col + 1);

    for (int num = 1; num <= N; num++) {
        if (isSafe(board, row, col, num)) {


 board[row][col] = num;
            if (solveSudokuUtil(board, row, col + 1))
                return true;
            board[row][col] = UNASSIGNED;
        }
    }

    return false;
}

void solveSudoku(vector<vector<int>>& board) {
    if (solveSudokuUtil(board, 0, 0)) {
        cout << "Sudoku puzzle solved:" << endl;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cout << board[i][j] << " ";
            }
            cout << endl;
        }
    } else {
        cout << "No solution exists for the given Sudoku puzzle." << endl;
    }
}

int main() {
    vector<vector<int>> board = {{5, 3, 0, 0, 7, 0, 0, 0, 0},
                                 {6, 0, 0, 1, 9, 5, 0, 0, 0},
                                 {0, 9, 8, 0, 0, 0, 0, 6, 0},
                                 {8, 0, 0, 0, 6, 0, 0, 0, 3},
                                 {4, 0, 0, 8, 0, 3, 0, 0, 1},
                                 {7, 0, 0, 0, 2, 0, 0, 0, 6},
                                 {0, 6, 0, 0, 0, 0, 2, 8, 0},
                                 {0, 0, 0, 4, 1, 9, 0, 0, 5},
                                 {0, 0, 0, 0, 8, 0, 0, 7, 9}};

    solveSudoku(board);

    return 0;
}

15. Implement the Backtracking algorithm for Hamiltonian Cycle.

C++

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

#define V 5

void printSolution(vector<int>& path) {
    cout << "Hamiltonian Cycle: ";
    for (int vertex : path) {
        cout << vertex << " ";
    }
    cout << path[0] << endl;
}

bool isSafe(int vertex, vector<vector<int>>& graph, vector<int>& path, int pos) {
    if (graph[path[pos - 1]][vertex] == 0)
        return false;

    for (int i = 0; i < pos; i++) {
        if (path[i] == vertex)
            return false;
    }

    return true;
}

bool hamiltonianCycleUtil(vector<vector<int>>& graph, vector<int>& path, int pos) {
    if (pos == V) {
        if (graph[path[pos - 1]][path[0]] == 1)
            return true;
        else
            return false;
    }

    for (int vertex = 1; vertex < V; vertex++) {
        if (isSafe(vertex, graph, path, pos)) {
            path[pos] = vertex;
            if (hamiltonianCycleUtil(graph, path, pos + 1))
                return true;
            path[pos] = -1;
        }
    }

    return false;
}

void hamiltonianCycle(vector<vector<int>>& graph) {
    vector<int> path(V, -1);
    path[0] = 0;



 if (hamiltonianCycleUtil(graph, path, 1))
        printSolution(path);
    else
        cout << "No Hamiltonian Cycle exists for the given graph." << endl;
}

int main() {
    vector<vector<int>> graph = {{0, 1, 0, 1, 0},
                                 {1, 0, 1, 1, 1},
                                 {0, 1, 0, 0, 1},
                                 {1, 1, 0, 0, 1},
                                 {0, 1, 1, 1, 0}};

    hamiltonianCycle(graph);

    return 0;
}

16. Print all Hamiltonian paths present in a graph.

C++

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

void printPath(vector<int>& path) {
    for (int vertex : path) {
        cout << vertex << " ";
    }
    cout << endl;
}

bool isSafe(int vertex, vector<vector<int>>& graph, vector<int>& path, int pos) {
    if (graph[path[pos - 1]][vertex] == 0)
        return false;

    for (int i = 0; i < pos; i++) {
        if (path[i] == vertex)
            return false;
    }

    return true;
}

void hamiltonianPathUtil(vector<vector<int>>& graph, vector<int>& path, int pos) {
    if (pos == graph.size()) {
        printPath(path);
        return;
    }

    for (int vertex = 1; vertex < graph.size(); vertex++) {
        if (isSafe(vertex, graph, path, pos)) {
            path[pos] = vertex;
            hamiltonianPathUtil(graph, path, pos + 1);
            path[pos] = -1;
        }
    }
}

void hamiltonianPath(vector<vector<int>>& graph) {
    vector<int> path(graph.size(), -1);
    path[0] = 0;

    hamiltonianPathUtil(graph, path, 1);
}

int main() {
    vector<vector<int>> graph = {{0, 1, 1, 1},
                                 {1, 0, 1, 0},
                                 {1, 1, 0, 1},
                                 {1, 0, 1, 0}};

    hamiltonianPath(graph);

    return 0;
}

17. Find all paths from a source to a destination in a graph.

C++

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

void printPath(vector<int>& path) {
    for (int vertex : path) {
        cout << vertex << " ";
    }
    cout << endl;
}

void findPathsUtil(int source, int destination, vector<vector<int>>& graph, vector<int>& path, vector<bool>& visited) {
    visited[source] = true;
    path.push_back(source);

    if (source == destination) {
        printPath(path);
    } else {
        for (int neighbor : graph[source]) {
            if (!visited[neighbor]) {
                findPathsUtil(neighbor, destination, graph, path, visited);
            }
        }
    }

    visited[source] = false;
    path.pop_back();
}

void findPaths(int source, int destination, vector<vector<int>>& graph) {
    vector<bool> visited(graph.size(), false);
    vector<int> path;

    findPathsUtil(source, destination, graph, path, visited);
}

int main() {
    vector<vector<int>> graph = {{1, 2},       // Node 0
                                 {0, 2, 3},    // Node 1
                                 {0, 1, 3},    // Node 2
                                 {1, 2}};      // Node 3

    int source = 0;
    int destination = 3;

    findPaths(source, destination, graph);

    return 0;
}

18. Generate all possible sorted arrays from alternate elements of two given sorted arrays.

C++

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

void generateSortedArraysUtil(vector<int>& arr1, vector<int>& arr2, vector<int>& result, int i, int j, int m, int

 n, bool isEven) {
    if (isEven) {
        if (result.size() > 0) {
            for (int element : result) {
                cout << element << " ";
            }
            cout << endl;
        }
    }

    for (int k = i; k < m; k++) {
        if (result.empty() || arr1[k] > result.back()) {
            result.push_back(arr1[k]);
            generateSortedArraysUtil(arr1, arr2, result, k + 1, j, m, n, !isEven);
            result.pop_back();
        }
    }

    for (int k = j; k < n; k++) {
        if (result.empty() || arr2[k] > result.back()) {
            result.push_back(arr2[k]);
            generateSortedArraysUtil(arr1, arr2, result, i, k + 1, m, n, !isEven);
            result.pop_back();
        }
    }
}

void generateSortedArrays(vector<int>& arr1, vector<int>& arr2) {
    int m = arr1.size();
    int n = arr2.size();

    vector<int> result;

    generateSortedArraysUtil(arr1, arr2, result, 0, 0, m, n, true);
}

int main() {
    vector<int> arr1 = {10, 15, 25};
    vector<int> arr2 = {5, 20, 30};

    generateSortedArrays(arr1, arr2);

    return 0;
}

19. Find maximum number possible by doing at most K swaps.

C++

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

void findMaximumNumberUtil(string& number, int k, string& maximumNumber, int currentIndex, int& maxIndex) {
    if (k == 0) {
        return;
    }

    int n = number.length();
    char currentDigit = number[currentIndex];

    for (int i = currentIndex + 1; i < n; i++) {
        if (number[i] > currentDigit) {
            swap(number[currentIndex], number[i]);

            if (number.compare(maximumNumber) > 0) {
                maximumNumber = number;
                maxIndex = currentIndex;
            }

            findMaximumNumberUtil(number, k - 1, maximumNumber, currentIndex + 1, maxIndex);

            swap(number[currentIndex], number[i]);
        }
    }

    if (currentIndex == maxIndex) {
        findMaximumNumberUtil(number, k, maximumNumber, currentIndex + 1, maxIndex);
    }
}

string findMaximumNumber(string number, int k) {
    string maximumNumber = number;
    int maxIndex = -1;

    findMaximumNumberUtil(number, k, maximumNumber, 0, maxIndex);

    return maximumNumber;
}

int main() {
    string number = "129814999";
    int k = 4;

    string maximumNumber = findMaximumNumber(number, k);

    cout << "Maximum Number: " << maximumNumber << endl;

    return 0;
}

20. Print all distinct permutations of a given string with duplicates.

C++

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

void permuteUtil(string& str, int l, int r, unordered_set<string>& uniquePermutations) {
    if (l == r) {
        uniquePermutations.insert(str);
        return;
    }

    for (int i = l; i <= r; i++) {
        swap(str[l], str[i]);
        permuteUtil(str, l + 1,

 r, uniquePermutations);
        swap(str[l], str[i]);
    }
}

void printDistinctPermutations(string str) {
    unordered_set<string> uniquePermutations;

    permuteUtil(str, 0, str.length() - 1, uniquePermutations);

    for (const string& permutation : uniquePermutations) {
        cout << permutation << endl;
    }
}

int main() {
    string str = "ABA";

    cout << "Distinct Permutations:" << endl;
    printDistinctPermutations(str);

    return 0;
}

21. Find the shortest possible route in a minefield.

C++

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

int findShortestRoute(vector<vector<int>>& minefield, int startRow, int startCol, int endRow, int endCol) {
    int m = minefield.size();
    int n = minefield[0].size();

    vector<vector<int>> distance(m, vector<int>(n, INT_MAX));
    vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    distance[startRow][startCol] = 0;
    queue<pair<int, int>> q;
    q.push({startRow, startCol});

    while (!q.empty()) {
        pair<int, int> curr = q.front();
        q.pop();

        for (pair<int, int>& dir : directions) {
            int newRow = curr.first + dir.first;
            int newCol = curr.second + dir.second;

            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && minefield[newRow][newCol] == 1 && distance[newRow][newCol] == INT_MAX) {
                distance[newRow][newCol] = distance[curr.first][curr.second] + 1;
                q.push({newRow, newCol});
            }
        }
    }

    return distance[endRow][endCol];
}

int main() {
    vector<vector<int>> minefield = {{1, 0, 1, 1},
                                     {1, 1, 1, 0},
                                     {0, 0, 1, 1},
                                     {0, 0, 0, 1}};
    int startRow = 0;
    int startCol = 0;
    int endRow = 3;
    int endCol = 3;

    int shortestRoute = findShortestRoute(minefield, startRow, startCol, endRow, endCol);

    cout << "Shortest Route: " << shortestRoute << endl;

    return 0;
}

22. Find the largest number in a sequence of numbers that can be obtained by deleting some numbers without changing the order of remaining digits.

C++

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

string findLargestNumber(string sequence) {
    int n = sequence.length();

    string largestNumber = "";
    char maxDigit = '0';

    for (int i = 0; i < n; i++) {
        if (sequence[i] >= maxDigit) {
            largestNumber += sequence[i];
            maxDigit = sequence[i];
        }
    }

    return largestNumber;
}

int main() {
    string sequence = "132845";

    string largestNumber = findLargestNumber(sequence);

    cout << "Largest Number: " << largestNumber << endl;

    return 0;
}

23. Find the K-th permutation of a string.

C++

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string findKthPermutation(string str, int k) {
    sort(str.begin(), str.end());

    int count = 1;

    while (count < k) {
        next_permutation(str.begin(), str.end());
        count++;
    }

    return str;
}

int main() {
    string str = "ABC";
    int k = 3;

    string

 kthPermutation = findKthPermutation(str, k);

    cout << "K-th Permutation: " << kthPermutation << endl;

    return 0;
}

24. Solve the m Coloring Decision problem (given an undirected graph and a number m, determine if the graph can be colored with at most m colors).

C++

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

bool isSafe(int node, vector<vector<int>>& graph, vector<int>& color, int c) {
    for (int neighbor : graph[node]) {
        if (color[neighbor] == c) {
            return false;
        }
    }

    return true;
}

bool graphColoringUtil(vector<vector<int>>& graph, vector<int>& color, int m, int node) {
    int n = graph.size();

    if (node == n) {
        return true;
    }

    for (int c = 1; c <= m; c++) {
        if (isSafe(node, graph, color, c)) {
            color[node] = c;

            if (graphColoringUtil(graph, color, m, node + 1)) {
                return true;
            }

            color[node] = 0;
        }
    }

    return false;
}

bool graphColoring(vector<vector<int>>& graph, int m) {
    int n = graph.size();

    vector<int> color(n, 0);

    return graphColoringUtil(graph, color, m, 0);
}

int main() {
    vector<vector<int>> graph = {{0, 1, 1, 1},
                                 {1, 0, 1, 0},
                                 {1, 1, 0, 1},
                                 {1, 0, 1, 0}};
    int m = 3;

    bool isColorable = graphColoring(graph, m);

    cout << "Is Colorable with " << m << " colors: " << (isColorable ? "Yes" : "No") << endl;

    return 0;
}

25. Find if there is a subset of a given set with sum equal to zero.

C++

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

bool isSubsetSumZero(vector<int>& nums) {
    int n = nums.size();
    int sum = 0;

    for (int i = 0; i < n; i++) {
        sum += nums[i];
    }

    if (sum == 0) {
        return true;
    }

    if (sum % 2 != 0) {
        return false;
    }

    vector<vector<bool>> dp(n + 1, vector<bool>(sum / 2 + 1, false));

    for (int i = 0; i <= n; i++) {
        dp[i][0] = true;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= sum / 2; j++) {
            if (j < nums[i - 1]) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
            }
        }
    }

    return dp[n][sum / 2];
}

int main() {
    vector<int> nums = {1, 2, -3, 4, 5};

    bool hasSubsetSumZero = isSubsetSumZero(nums);

    cout << "Has

 Subset Sum Zero: " << (hasSubsetSumZero ? "Yes" : "No") << endl;

    return 0;
}

26. Find all Stepping Numbers in a range (A Stepping Number is a number defined as a number whose adjacent digits have an absolute difference of 1).

C++

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

vector<int> steppingNumbers(int start, int end) {
    vector<int> result;

    queue<int> q;

    for (int i = 1; i <= 9; i++) {
        q.push(i);
    }

    if (start == 0) {
        result.push_back(0);
    }

    while (!q.empty()) {
        int num = q.front();
        q.pop();

        if (num >= start && num <= end) {
            result.push_back(num);
        }

        if (num > end) {
            continue;
        }

        int lastDigit = num % 10;

        if (lastDigit > 0) {
            q.push(num * 10 + (lastDigit - 1));
        }

        if (lastDigit < 9) {
            q.push(num * 10 + (lastDigit + 1));
        }
    }

    return result;
}

int main() {
    int start = 10;
    int end = 100;

    vector<int> result = steppingNumbers(start, end);

    cout << "Stepping Numbers between " << start << " and " << end << ": ";
    for (int num : result) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

27. Find all combinations of elements satisfying given constraints.

C++

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

void findCombinationsUtil(vector<int>& nums, int target, int start, vector<int>& current, vector<vector<int>>& result) {
    if (target == 0) {
        result.push_back(current);
        return;
    }

    for (int i = start; i < nums.size(); i++) {
        if (nums[i] > target) {
            break;
        }

        current.push_back(nums[i]);
        findCombinationsUtil(nums, target - nums[i], i + 1, current, result);
        current.pop_back();
    }
}

vector<vector<int>> findCombinations(vector<int>& nums, int target) {
    vector<vector<int>> result;
    vector<int> current;

    findCombinationsUtil(nums, target, 0, current, result);

    return result;
}

int main() {
    vector<int> nums = {2, 3, 6, 7};
    int target = 7;

    vector<vector<int>> result = findCombinations(nums, target);

    cout << "Combinations for Target " << target << ":" << endl;
    for (vector<int>& combination : result) {
        for (int num : combination) {
            cout << num << " ";
        }
        cout << endl;
    }

    return 0;
}

28. Find Longest Possible Route in a Matrix with Hurdles.

C++

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

bool isValid(int x, int y, vector<vector<int>>& matrix, vector<vector<bool>>& visited) {
    int rows = matrix.size();
    int cols = matrix[0].size();

    return x >= 0 && x < rows && y >= 0 && y < cols && matrix[x][y] == 1 && !visited[x][y];
}

int findLongestRoute(vector<vector<int>>& matrix, pair<int, int> source, pair<int, int> destination) {


    int rows = matrix.size();
    int cols = matrix[0].size();

    vector<vector<bool>> visited(rows, vector<bool>(cols, false));

    queue<pair<pair<int, int>, int>> q;
    q.push(make_pair(source, 0));
    visited[source.first][source.second] = true;

    int maxDistance = 0;

    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};

    while (!q.empty()) {
        pair<pair<int, int>, int> current = q.front();
        q.pop();

        int x = current.first.first;
        int y = current.first.second;
        int distance = current.second;

        if (x == destination.first && y == destination.second) {
            maxDistance = max(maxDistance, distance);
            break;
        }

        for (int i = 0; i < 4; i++) {
            int newX = x + dx[i];
            int newY = y + dy[i];

            if (isValid(newX, newY, matrix, visited)) {
                q.push(make_pair(make_pair(newX, newY), distance + 1));
                visited[newX][newY] = true;
            }
        }
    }

    return maxDistance;
}

int main() {
    vector<vector<int>> matrix = {
        {1, 0, 1, 1, 1},
        {1, 0, 1, 0, 1},
        {1, 1, 1, 0, 1},
        {0, 0, 0, 0, 1},
        {1, 1, 1, 0, 1}
    };

    pair<int, int> source = make_pair(0, 0);
    pair<int, int> destination = make_pair(4, 4);

    int longestRoute = findLongestRoute(matrix, source, destination);

    cout << "Longest Possible Route: " << longestRoute << endl;

    return 0;
}

29. Implement wildcard pattern matching algorithm.

C++

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

bool isMatch(string str, string pattern) {
    int m = str.length();
    int n = pattern.length();

    bool dp[m + 1][n + 1];
    memset(dp, false, sizeof(dp));

    dp[0][0] = true;

    for (int j = 1; j <= n; j++) {
        if (pattern[j - 1] == '*') {
            dp[0][j] = dp[0][j - 1];
        }
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (str[i - 1] == pattern[j - 1] || pattern[j - 1] == '?') {
                dp[i][j] = dp[i - 1][j - 1];
            } else if (pattern[j - 1] == '*') {
                dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
            }
        }
    }

    return dp[m][n];
}

int main() {
    string str = "leetcode";
    string pattern = "*t?co*";

    bool isPatternMatch = isMatch(str, pattern);

    if (isPatternMatch) {
        cout << "Pattern matches the string." << endl;
    } else {
        cout << "Pattern does not match

 the string." << endl;
    }

    return 0;
}

30. Print all Palindromic Partitions of a String.

C++

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

bool isPalindrome(string str, int start, int end) {
    while (start <= end) {
        if (str[start] != str[end]) {
            return false;
        }
        start++;
        end--;
    }
    return true;
}

void findPalindromicPartitions(string str, int start, vector<string>& current, vector<vector<string>>& result) {
    if (start == str.length()) {
        result.push_back(current);
        return;
    }

    for (int i = start; i < str.length(); i++) {
        if (isPalindrome(str, start, i)) {
            current.push_back(str.substr(start, i - start + 1));
            findPalindromicPartitions(str, i + 1, current, result);
            current.pop_back();
        }
    }
}

vector<vector<string>> palindromicPartitions(string str) {
    vector<vector<string>> result;
    vector<string> current;

    findPalindromicPartitions(str, 0, current, result);

    return result;
}

int main() {
    string str = "nitin";

    vector<vector<string>> partitions = palindromicPartitions(str);

    cout << "Palindromic Partitions of " << str << ":" << endl;
    for (vector<string>& partition : partitions) {
        for (string palindromic : partition) {
            cout << palindromic << " ";
        }
        cout << endl;
    }

    return 0;
}

31. Solve the Tug of War problem (divide an array into two subsets with minimum difference).

C++

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

void tugOfWar(vector<int>& nums, vector<bool>& currentSet, vector<bool>& minSet, int currentIndex, int currentSum, int totalSum, int& minDiff) {
    if (currentIndex == nums.size()) {
        int remainingSum = totalSum - currentSum;
        int diff = abs(currentSum - remainingSum);

        if (diff < minDiff) {
            minDiff = diff;
            minSet = currentSet;
        }
        return;
    }

    currentSet[currentIndex] = true;
    tugOfWar(nums, currentSet, minSet, currentIndex + 1, currentSum + nums[currentIndex], totalSum, minDiff);

    currentSet[currentIndex] = false;
    tugOfWar(nums, currentSet, minSet, currentIndex + 1, currentSum, totalSum, minDiff);
}

void printTugOfWarSolution(vector<int>& nums, vector<bool>& minSet, vector<bool>& maxSet) {
    cout << "Subset 1: ";
    for (int i = 0; i < nums.size(); i++) {
        if (minSet[i]) {
            cout << nums[i] << " ";
        }
    }
    cout << endl;

    cout << "Subset 2: ";
    for (int i = 0; i < nums.size(); i++) {
        if (!minSet[i]) {
            cout << nums[i] << " ";
        }
    }
    cout << endl;
}

void tugOfWarSolver(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) {
        return;
    }

    int totalSum = 0;
    for (int num : nums) {
        totalSum += num;
    }

    vector<bool> currentSet(n, false);
    vector<bool> minSet(n, false);
    int minDiff = INT_MAX;

    tugOfWar(nums, currentSet, minSet, 0, 0, totalSum, minDiff);

    printTugOfWarSolution(nums, minSet, minSet);
}

int main() {
    vector<int> nums = {1, 2, 3, 4, 5, 6};

    tugOfWarSolver(nums);

    return 0;
}

32. Find ways to calculate a target from elements of specified array.

C++

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

void calculateTarget(vector<int>& nums, int target, vector<int>& current, int currentIndex, int currentSum) {
    if (currentSum == target) {
        for (int i = 0; i < current.size(); i++) {
            cout << current[i];
            if (i != current.size() - 1) {
                cout << " + ";
            }
        }
        cout << endl;
        return;
    }

    for (int i = currentIndex; i < nums.size(); i++) {
        if (currentSum + nums[i] <= target) {
            current.push_back(nums[i]);
            calculateTarget(nums, target, current, i, currentSum + nums[i]);
            current.pop_back();
        }
    }
}

void calculateTargetSolver(vector<int>& nums, int target) {
    vector<int> current;
    calculateTarget(nums, target, current, 0, 0);
}

int main() {
    vector<int> nums = {2, 3, 6, 7};
    int target = 7;



    calculateTargetSolver(nums, target);

    return 0;
}

33. Determine if a given number can be represented as the sum of two cubes.

C++

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

bool isSumOfTwoCubes(int num) {
    unordered_set<int> cubes;

    for (int i = 1; i * i * i <= num; i++) {
        int cube = i * i * i;
        cubes.insert(cube);

        if (cubes.count(num - cube) > 0) {
            return true;
        }
    }

    return false;
}

int main() {
    int num = 4104;

    if (isSumOfTwoCubes(num)) {
        cout << num << " can be represented as the sum of two cubes." << endl;
    } else {
        cout << num << " cannot be represented as the sum of two cubes." << endl;
    }

    return 0;
}

34. Find all possible interpretations of an array of digits.

C++

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

void findAllInterpretationsHelper(vector<int>& digits, int index, string interpretation, vector<string>& interpretations) {
    if (index == digits.size()) {
        interpretations.push_back(interpretation);
        return;
    }

    int currentDigit = digits[index];
    char currentChar = 'A' + currentDigit - 1;
    findAllInterpretationsHelper(digits, index + 1, interpretation + currentChar, interpretations);

    if (index < digits.size() - 1) {
        int nextDigit = digits[index + 1];
        int number = currentDigit * 10 + nextDigit;
        if (number <= 26) {
            currentChar = 'A' + number - 1;
            findAllInterpretationsHelper(digits, index + 2, interpretation + currentChar, interpretations);
        }
    }
}

vector<string> findAllInterpretations(vector<int>& digits) {
    vector<string> interpretations;
    string interpretation;

    findAllInterpretationsHelper(digits, 0, interpretation, interpretations);

    return interpretations;
}

int main() {
    vector<int> digits = {1, 2, 1};

    vector<string> interpretations = findAllInterpretations(digits);

    cout << "All possible interpretations of ";
    for (int digit : digits) {
        cout << digit;
    }
    cout << ":" << endl;
    for (string interpretation : interpretations) {
        cout << interpretation << endl;
    }

    return 0;
}

35. Print all combinations of points that can compose a given number.

C++

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

void printCombinationsHelper(vector<int>& nums, int target, vector<int>& currentCombination, int currentIndex) {
    if (target == 0) {
        for (int i = 0; i < currentCombination.size(); i++) {
            cout << currentCombination[i];
            if (i != currentCombination.size() - 1) {
                cout << " + ";
            }
        }
        cout << endl;
        return;
    }

    for (int i = currentIndex; i < nums.size(); i++) {
        if (target - nums[i] >= 0) {
            currentCombination.push_back(nums[i]);
            printCombinationsHelper(nums, target - nums[i], currentCombination, i);
            currentCombination.pop_back();
        }
    }
}

void printCombinations(vector<int>& nums, int target) {
    vector<int>

 currentCombination;
    printCombinationsHelper(nums, target, currentCombination, 0);
}

int main() {
    vector<int> nums = {2, 3, 6, 7};
    int target = 7;

    printCombinations(nums, target);

    return 0;
}

36. Solve the Word Break Problem.

C++

#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;

bool wordBreakHelper(string s, unordered_set<string>& wordDict, int startIndex, vector<bool>& memo) {
    if (startIndex == s.length()) {
        return true;
    }

    if (memo[startIndex]) {
        return false;
    }

    for (int i = startIndex + 1; i <= s.length(); i++) {
        string prefix = s.substr(startIndex, i - startIndex);
        if (wordDict.count(prefix) > 0 && wordBreakHelper(s, wordDict, i, memo)) {
            return true;
        }
    }

    memo[startIndex] = true;
    return false;
}

bool wordBreak(string s, unordered_set<string>& wordDict) {
    vector<bool> memo(s.length() + 1, false);
    return wordBreakHelper(s, wordDict, 0, memo);
}

int main() {
    string s = "leetcode";
    unordered_set<string> wordDict = {"leet", "code"};

    if (wordBreak(s, wordDict)) {
        cout << "The string can be segmented into words from the dictionary." << endl;
    } else {
        cout << "The string cannot be segmented into words from the dictionary." << endl;
    }

    return 0;
}

37. Generate all binary strings from a given pattern.

C++

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

void