1.

Consider a rat placed at position (0, 0) in an n x n square

matrix maze[][]. The rat's goal is to reach the destination at
position (n-1, n-1). The rat can move in four possible
directions: 'U'(up), 'D'(down), 'L' (left), 'R' (right).

The matrix contains only two possible values:

 0: A blocked cell through which the rat cannot travel.

 1: A free cell that the rat can pass through.
Your task is to find all possible paths the rat can take to
reach the destination, starting from (0, 0) and ending at (n-1, n-
1), under the condition that the rat cannot revisit any cell
along the same path. Furthermore, the rat can only move to
adjacent cells that are within the bounds of the matrix and not
blocked.
If no path exists, return an empty list.

Note: Return the final result vector in lexicographically

smallest order.

Examples:

Input: maze[][] = [[1, 0, 0, 0], [1, 1, 0, 1], [1, 1,

0, 0], [0, 1, 1, 1]]
Output: ["DDRDRR", "DRDDRR"]
Explanation: The rat can reach the destination at (3,
3) from (0, 0) by two paths - DRDDRR and DDRDRR, when
printed in sorted order we get DDRDRR DRDDRR.
Input: maze[][] = [[1, 0], [1, 0]]
Output: []
Explanation: No path exists as the destination cell
(1, 1) is blocked.
Input: maze[][] = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
Output: ["DDRR", "RRDD"]
Explanation: The rat has two possible paths to reach
the destination: DDRR and RRDD.
Constraints:
2≤n≤5
0 ≤ maze[i][j] ≤ 1
2. Given an integer n, the task is to find all distinct solutions to
the n-queens problem, where n queens are placed on an n *
n chessboard such that no two queens can attack each other.
Note: Each solution is a unique configuration of n queens,
represented as a permutation of [1,2,3,....,n]. The number at
the ith position indicates the row of the queen in the ith column.
For example, [3,1,4,2] shows one such layout.
Example:
Input: n = 4
Output: [2, 4, 1, 3], [3, 1, 4, 2]

Explanation : These are the 2 possible solutions.

Input: n = 2
Output: []
Explanation: No solution, as queens can attack each other in all
possible configurations.
Table of Content
 [Naive Approach] By Generating all Permutations using
Recursion
 [Expected Approach] Using Backtracking with Pruning
 [Alternate Approach] Backtracking Using Bit-masking
[Naive Approach] - Using Recursion - O(n! * n) Time
and O(n) Space
A simple idea to solve the N-Queens problem is to generate all
possible permutations of [1, 2, 3, ..., n] and then check if it
represents a valid N-Queens configuration. Since each queen has
to be in a different row and column, using permutations
automatically takes care of those rules. But we still need to
check that no two queens are on the same diagonal.
Below is given the implementation:

//C++ program to find all solution of N queen problem

//using recursion
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;

// Function to check if the current placement is safe

bool isSafe(vector<int>& board, int currRow,
int currCol) {

// Check all previously placed queens

for(int i = 0; i < [Link](); ++i) {
int placedRow = board[i];

// Columns are 1-based

int placedCol = i + 1;

// Check if the queen is on the same diagonal

if(abs(placedRow - currRow) == abs(placedCol - currCol)) {
return false; // Not safe
}
}

// Safe to place the queen

return true;
}

// Recursive function to generate all possible permutations

void nQueenUtil(int col, int n, vector<int>& board,
vector<vector<int>>& res, vector<bool>& visited) {

// If all queens are placed, add into res

if(col > n) {
res.push_back(board);
return;
}

// Try placing a queen in each row

 // of the current column
for(int row = 1; row <= n; ++row) {

// Check if the row is already used

if(!visited[row]) {

// Check if it's safe to place the queen

if(isSafe(board, row, col)) {

// Mark the row as used

visited[row] = true;

// Place the queen

board.push_back(row);

// Recur to place the next queen

nQueenUtil(col + 1, n, board,
res, visited);

// Backtrack: remove the queen

board.pop_back();

// Unmark row
visited[row] = false;
}
}
}
}

// Main function to find all distinct

// res to the n-queens puzzle
vector<vector<int>> nQueen(int n) {
vector<vector<int>> res;

// Current board configuration

vector<int> board;

// Track used rows

vector<bool> visited(n + 1, false);

// Start solving from the first column

nQueenUtil(1, n, board, res, visited);
return res;
}

int main() {
int n = 4;
vector<vector<int>> res = nQueen(n);
 for(int i = 0;i < [Link](); i++) {
cout << "[";
for(int j = 0; j < n; ++j) {
cout << res[i][j];
if(j != n - 1) cout << " ";
}
cout << "]\n";
}
return 0;
}

Output
[2 4 1 3]
[3 1 4 2]
Time Complexity: O(n!*n), n! for generating
all permutations and O(n) for validation of each permutation.
Auxiliary Space: O(n)
[Expected Approach] - Using Backtracking with
Pruning - O(n!) Time and O(n) Space
To optimise the above approach, we can use backtracking
with pruning. Instead of generating all possible permutations,
we build the solution incrementally, while doing this we can
make sure at each step that the partial solution remains valid. If
a conflict occur then we'll backtrack immediately, this helps in
avoiding unnecessary computations.
Step-by-step implementation:
 Start from the first column and try placing a queen in each
row.
 Keep arrays to track which rows are already occupied.
Similarly, for tracking major and minor diagonals are
already occupied.
 If a queen placement conflicts with existing
queens, skip that row and backtrack the queen to try the
next possible row (Prune and backtrack during conflict).

// C++ program to find all solution of N queen problem by

// using backtracking and pruning

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

// Utility function for solving the N-Queens

// problem using backtracking.
void nQueenUtil(int j, int n, vector<int> &board, vector<bool> &rows,
vector<bool> &diag1, vector<bool> &diag2, vector<vector<int>>
&res) {

if (j > n) {
// A solution is found
res.push_back(board);
return;
}
for (int i = 1; i <= n; ++i) {
if (!rows[i] && !diag1[i + j] && !diag2[i - j + n]) {

// Place queen
rows[i] = diag1[i + j] = diag2[i - j + n] = true;
board.push_back(i);

// Recurse to the next column

nQueenUtil(j + 1, n, board, rows, diag1, diag2, res);

// Remove queen (backtrack)

board.pop_back();
rows[i] = diag1[i + j] = diag2[i - j + n] = false;
}
}
}

// Solves the N-Queens problem and returns

// all valid configurations.
vector<vector<int>> nQueen(int n) {
vector<vector<int>> res;
vector<int> board;

// Rows occupied
vector<bool> rows(n + 1, false);

// Major diagonals (row + j) and Minor diagonals (row - col + n)

vector<bool> diag1(2 * n + 1, false);
vector<bool> diag2(2 * n + 1, false);

// Start solving from the first column

nQueenUtil(1, n, board, rows, diag1, diag2, res);
return res;
}

int main() {
 int n = 4;
vector<vector<int>> res = nQueen(n);

for (int i = 0; i < [Link](); i++) {

cout << "[";
for (int j = 0; j < n; ++j) {
cout << res[i][j];
if (j != n - 1)
cout << " ";
}
cout << "]\n";
}
return 0;
}

Output
[2 4 1 3]
[3 1 4 2]
Time complexity: O(n!) For generating all permutations.
Auxiliary Space: O(n)
[Alternate Approach] - Backtracking Using Bit-
masking
To further optimise the backtracking approach, especially for
larger values of n, we can use bit-masking to efficiently track
occupied rows and diagonals. Bit-masking lets us to use
integers (rows, ld, rd) to track which rows and diagonals are
occupied, making use of fast bitwise operations for quicker
calculations. The approach remains the same as above.
Below is given the implementation:

//C++ program to find all solution of N queen problem

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

// Function to check if the current placement is safe

bool isSafe(int row, int col, int rows, int ld, int rd, int n) {
return !((rows >> row) & 1) && !((ld >> (row + col)) & 1) && !((rd >>
(row - col + n)) & 1);
}

// Recursive function to generate all possible permutations

void nQueenUtil(int col, int n, vector<int>& board,
vector<vector<int>>& res, int rows, int ld, int rd) {

// If all queens are placed, add into res

if(col > n) {
res.push_back(board);
return;
}

// Try placing a queen in each row

// of the current column
for(int row = 1; row <= n; ++row) {

// Check if it's safe to place the queen

if(isSafe(row, col, rows, ld, rd, n)) {

// Place the queen

board.push_back(row);

// Recur to place the next queen

nQueenUtil(col + 1, n, board,
res, rows | (1 << row),
(ld | (1 << (row + col))),
(rd | (1 << (row - col + n))));

// Backtrack: remove the queen

board.pop_back();
}
}

// Main function to find all distinct

// res to the n-queens puzzle
vector<vector<int>> nQueen(int n) {
vector<vector<int>> res;

// Current board configuration

vector<int> board;

// Start solving from the first column

nQueenUtil(1, n, board, res, 0, 0, 0);
return res;
}

int main() {
int n = 4;
vector<vector<int>> res = nQueen(n);
 for(int i = 0;i < [Link](); i++) {
cout << "[";
for(int j = 0; j < n; ++j) {
cout << res[i][j];
if(j != n - 1) cout << " ";
}
cout << "]\n";
}
return 0;
}

Output
[2 4 1 3]
[3 1 4 2]
Time Complexity: O(n!), for generating all permutations.
Space Complexity: O(n)

3. Given a string s and a dictionary dict[] of valid words, you

need to return all possible ways to break the
string s into sentence such that each word in the sentence is a
valid dictionary word.
You are allowed to use a valid word multiple times in the
sentence.

Examples:

Input: s = "likegfg", dict[] = ["lik", "like",

"egfg", "gfg"]
Output:
"lik egfg"
"like gfg"
Explanation: All the words in the given sentences are
present in the dictionary.
Input: s = "geeksforgeeks", dict[] = ["for", "geeks"]
Output: "geeks for geeks"
Explanation: The string "geeksforgeeks" can be broken
into valid words from the dictionary in one way.
Constraints:
1 ≤ [Link]() ≤ 20
1 ≤ dict[i] ≤ 15
1 ≤ [Link]() ≤ 500
4. Given a string s that contains parentheses and letters, remove the minimum
number of invalid parentheses to make the input string valid.

Return a list of unique strings that are valid with the minimum number of
removals. You may return the answer in any order.

Example 1:

Input: s = "()())()"
Output: ["(())()","()()()"]

Example 2:

Input: s = "(a)())()"
Output: ["(a())()","(a)()()"]

Example 3:

Input: s = ")("
Output: [""]

Constraints:

 1 <= [Link] <= 25

 s consists of lowercase English letters and parentheses '(' and ')'.
 There will be at most 20 parentheses in s.

5. Given an incomplete Sudoku in the form of matrix mat[][] of

order 9*9, the task is to solve the Sudoku. It is guaranteed that
the input Sudoku will have exactly one solution.

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each
column.
3. Each of the digits 1-9 must occur exactly once in each of the
9, 3x3 sub-boxes of the grid.
Note: Zeros represent blanks to be filled with numbers 1-9, while
non-zero cells are fixed and cannot be changed.

Examples:
Input: mat[][] =

Output:

Explanation: Each row, column and 3 x 3 box of the

output matrix contains unique numbers.
Input: mat[][] =

Output:
Explanation: Each row, column and 3 x 3 box of the
output matrix contains unique numbers.
Constraints:
0 ≤ mat[i][j] ≤ 9

6. You are given an undirected graph consisting of V vertices

and E edges represented by a list edges[][], along with an
integer m. Your task is to determine whether it is possible
to color the graph using at most m different colors such that
no two adjacent vertices share the same color. Return true if
the graph can be colored with at most m colors, otherwise
return false.

Note: The graph is indexed with 0-based indexing.

Examples:

Input: V = 4, edges[][] = [[0, 1], [1, 3], [2, 3],

[3, 0], [0, 2]], m = 3
Output: true
Explanation: It is possible to color the given graph
using 3 colors, for example, one of the possible ways
vertices can be colored as follows:
Vertex 0: Color 1
Vertex 1: Color 2
Vertex 2: Color 2
Vertex 3: Color 3
Input: V = 3, edges[][] = [[0, 1], [1, 2], [0, 2]], m
= 2
Output: false
Explanation: It is not possible to color the given
graph using only 2 colors because vertices 0, 1, and
2 form a triangle.
Constraints:
1 ≤ V ≤ 10
1 ≤ E = [Link]() ≤ (V*(V-1))/2
0 ≤ edges[i][j] ≤ V-1
1≤m≤V

7. Given a string s, find all possible ways to partition it such that

every substring in the partition is a palindrome.
Examples:
Input: s = "geeks"
Output: [[g, e, e, k, s], [g, ee, k, s]]
Explanation: [g, e, e, k, s] and [g, ee, k, s] are the only
partitions of "geeks" where each substring is a palindrome.
Input: s = "abcba"
Output: [[a, b, c, b, a], [a, bcb, a], [abcba]]
Explanation: [a, b, c, b, a], [a, bcb, a] and [abcba] are the only
partitions of "abcba" where each substring is a palindrome.
Table of Content
 [Approach 1] Using Recursion and Backtracking
 [Approach 2] Using Bit Manipulation
  [Expected Approach] Backtracking with Memoization
[Approach 1] Using Recursion and Backtracking
The main idea is to use backtracking to explore all combinations
of substrings starting from each index, including a substring in
the current partition only if it is a palindrome.
Step-By-Step Approach:
 Start at index 0 of the string.
 Generate all substrings starting from the current index.
 Check if the current substring is a palindrome.
 If it is, add it to the current partition path.
 Recursively continue from the next index.
 If the end of the string is reached, add the current path to the
result.
 Backtrack by removing the last added substring and try the
next possibility.

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

// Check if the given string is a palindrome

bool isPalindrome(string& s) {
int i = 0, j = [Link]() - 1;
while (i < j) {
if (s[i++] != s[j--])
return false;
}
return true;
}

// Recursive function to find all palindromic partitions

void backtrack(int idx, string& s, vector<string>& curr,
vector<vector<string>>& res) {

if (idx == [Link]()) {
// Store valid partition
res.push_back(curr);
return;
}

string temp = "";

 for (int i = idx; i < [Link](); ++i) {
temp += s[i];
if (isPalindrome(temp)) {
// Choose the substring
curr.push_back(temp);
// Explore further
backtrack(i + 1, s, curr, res);
// Backtrack
curr.pop_back();
}
}
}

// Return all palindromic partitions of string s

vector<vector<string>> palinParts(string& s) {
vector<vector<string>> res;
vector<string> curr;
backtrack(0, s, curr, res);
return res;
}

int main() {
string s = "geeks";

vector<vector<string>> res = palinParts(s);

// Print result: one partition per line

for (int i = 0; i < [Link](); ++i) {
for (int j = 0; j < res[i].size(); ++j) {
cout << res[i][j];
if (j != res[i].size() - 1) cout << " ";
}
cout << "\n";
}

return 0;
}

Output
g e e k s
g ee k s
Time Complexity: O(n × 2n), for exploring all possible partitions
(2n) and checking each substring for palindrome in O(n) time.
Auxiliary Space: O(n × 2n), for storing all palindromic partitions
and using recursion stack up to depth n.
[Approach 2] Using Bit Manipulation
The main idea is systematically explores all ways to cut a string
into parts and checks which ones consist only of palindromic
substrings. It uses binary representation to model cut/no-cut
choices between characters
 If there n characters in the string, then there are n-1 positions
to put a space or say cut the string.
 Each of these positions can be given a binary number 1 (If a
cut is made in this position) or 0 (If no cut is made in this
position).
 This will give a total of 2n-1 partitions and for each partition
check whether this partition is palindrome or not.
Illustration:
Input : geeks
0100 → ["ge","eks"] (not valid)
1011 → ["g","ee","k","s"] (valid)
1111 → ["g","e","e","k","s"] (valid)
0000 → ["geeks"] (not valid)

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

vector<vector<string>> ans;

// Check if all substrings in the partition are palindromes

bool isAllPalindromes(vector<string> &partition) {
for (auto &str : partition) {
int i = 0, j = [Link]() - 1;
while (i < j) {
if (str[i] != str[j])
return false;
i++;
j--;
}
}
return true;
}

// Generate partition of string based on the binary cut pattern

void createPartition(string &s, string &cutPattern) {

vector<string> currentPartition;
 string subStr;

// Start the first substring with the first character

subStr.push_back(s[0]);

for (int i = 0; i < [Link](); i++) {

// If no cut, append next character to current substring
if (cutPattern[i] == '0') {
subStr.push_back(s[i + 1]);
}
// If cut, push current substring and start a new one
else {
currentPartition.push_back(subStr);
[Link]();
subStr.push_back(s[i + 1]);
}
}

// Push the last substring

currentPartition.push_back(subStr);

// Store partition if all substrings are palindromes

if (isAllPalindromes(currentPartition)) {
ans.push_back(currentPartition);
}
}

// Recursively generate all cut patterns (bit strings)

void generateCut(string &s, string &cutPattern) {
// When pattern is complete, create partition
if ([Link]() == [Link]() - 1) {
createPartition(s, cutPattern);
return;
}

// Try with a cut

cutPattern.push_back('1');
generateCut(s, cutPattern);
cutPattern.pop_back();

// Try without a cut

cutPattern.push_back('0');
generateCut(s, cutPattern);
cutPattern.pop_back();
}

// Generate all palindromic partitions of the string

vector<vector<string>> palinParts(string &s) {
string cutPattern;
 generateCut(s, cutPattern);
return ans;
}

int main() {
string s = "geeks";
vector<vector<string>> result = palinParts(s);

for (auto &partition : result) {

for (auto &segment : partition) {
cout << segment << " ";
}
cout << "\n";
}

return 0;
}

Output
g e e k s
g ee k s
Time Complexity: O(n² × 2n) for generating all possible
partitions (2n) and checking each partition for palindromes (up to
O(n2) per partition).
Auxiliary Space: O(n × 2n), to store all palindromic partitions,
each potentially having up to n substrings.
[Expected Approach] Backtracking with
Memoization
The Idea is uses dynamic programming to precompute all
substrings of the input string that are palindromes in O(n²) time.
This precomputation helps in quickly checking whether a
substring is a palindrome during the recursive backtracking
phase. Then, it uses backtracking to explore all possible
partitions of the string and collects only those partitions where
every substring is a palindrome.

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

// Precompute all palindromic substrings in s

void palindromes(const string& s, vector<vector<bool>> &dp) {
int n = [Link]();

// All single characters are palindromes

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

// Check two-character substrings

for (int i = 0; i < n - 1; ++i)
dp[i][i + 1] = (s[i] == s[i + 1]);

// Check substrings of length 3 or more using bottom-up DP

for (int len = 3; len <= n; ++len) {
for (int i = 0; i <= n - len; ++i) {
int j = i + len - 1;
dp[i][j] = (s[i] == s[j]) && dp[i + 1][j - 1];
}
}
}

// Recursive function to find all palindromic partitions

void backtrack(int idx, const string& s, vector<string>& curr,
vector<vector<string>>& res, vector<vector<bool>> &dp) {

// If we have reached the end of the string, store current partition

if (idx == [Link]()) {
res.push_back(curr);
return;
}

// Try all substrings starting from index idx

for (int i = idx; i < [Link](); ++i) {
// If s[idx..i] is a palindrome, we can include it
if (dp[idx][i]) {
// Choose the substring
curr.push_back([Link](idx, i - idx + 1));
// Explore further from next index
backtrack(i + 1, s, curr, res, dp);
// Undo the choice (backtrack)
curr.pop_back();
}
}
}

// Return all palindromic partitions of string s

vector<vector<string>> palinParts(string& s) {

// DP table to store if substring s[i..j] is a palindrome

 vector<vector<bool>> dp([Link]()+1, vector<bool> ([Link]()+1,
false));

// Precompute all palindromic substrings using DP

palindromes(s, dp);

// Final result
vector<vector<string>> res;
// Current partition
vector<string> curr;
// Begin backtracking from index 0
backtrack(0, s, curr, res, dp);
return res;
}

int main() {
string s = "geeks";

// Get all palindromic partitions

vector<vector<string>> res = palinParts(s);

// Print each valid partition

for (auto& partition : res) {
for (auto& part : partition) {
cout << part << " ";
}
cout << "\n";
}

return 0;
}

Output
g e e k s
g ee k s
Time Complexity: O(n² + 2n×n), (n2) time for precomputing
palindromic substrings and O(2 n × n) for backtracking through all
partitions.
Auxiliary Space: O(n2), for the DP table and O(n) for the
recursion stack and temporary storage during backtracking.
A similar optimization can be applied to the bitmask-based
approach by precomputing all palindromic substrings in O(n²)
using dynamic programming. This reduces the palindrome-
checking time per partition from O(n) to O(1), thereby improving
the overall time complexity from O(n 2 × 2n) to O(n × 2n).
8. Given an array arr[], determine if it can be partitioned into
two subsets such that the sum of elements in both parts is
the same.

Note: Each element must be in exactly one subset.

Examples:

Input: arr = [1, 5, 11, 5]

Output: true
Explanation: The two parts are [1, 5, 5] and [11].
Input: arr = [1, 3, 5]
Output: false
Explanation: This array can never be partitioned into
two such parts.
Constraints:
1 ≤ [Link] ≤ 100
1 ≤ arr[i] ≤ 200

9. Given an integer n, consider an n × n chessboard. A Knight

starts at the top-left corner (0, 0) and must visit every cell
exactly once following the Knight’s standard moves in chess
(two steps in one direction and one step perpendicular).
 Return the n × n grid where each cell contains the step
number (starting from 0) at which the Knight visits that cell.
 If no valid tour exists, return -1.
Examples:
Input: n = 5
Output:
[[0, 5, 14, 9, 20],
[13, 8, 19, 4, 15],
[18, 1, 6, 21, 10],
[7, 12, 23, 16, 3],
[24, 17, 2, 11, 22]]
Explanation: Each number represents the step at which the
Knight visits that cell, starting from (0, 0) as step 0. The output
shows one valid Knight’s Tour on a 5×5 board.
Input: n = 3
Output: [-1]
Explanation: It is not possible to find a valid Knight's Tour on a
3x3 chessboard since the Knight cannot visit all 9 cells exactly
once without revisiting or getting stuck.
Table of Content
 [Approach -1] Using Recursion + Backtracking -
O(8^(n*n)) Time and O(n^2) Space
 [Approach -2] Using Warnsdorff's Algorithm - O(n^3)
Time and O(n^2) Space
[Approach -1] Using Recursion + Backtracking -
O(8n*n) Time and O(n2) Space
We will use recursion and backtracking to build a sequence of
knight moves that visits every cell once. Start at (0, 0), mark
each visited cell with the move number, and try all 8 knight
moves from the current cell. If a move leads to a dead end, undo
it (backtrack) and try the next move. Stop when you have placed
n*n moves (success) or exhausted all options (failure).

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

// 8 directions of knight moves

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

// Utility function to check if the

// move is valid
bool isSafe(int x, int y, int n, vector<vector<int>> &board) {
return (x >= 0 && y >= 0 && x < n &&
y < n && board[x][y] == -1);
}

// Recursive function to solve Knight's Tour

bool knightTourUtil(int x, int y, int step, int n, vector<vector<int>>
&board) {

// If all squares are visited

if (step == n * n) {
return true;
}

// Try all 8 possible knight moves

for (int i = 0; i < 8; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
 if (isSafe(nx, ny, n, board)) {
board[nx][ny] = step;

if (knightTourUtil(nx, ny, step + 1, n, board)) {

return true;
}

// Backtrack
board[nx][ny] = -1;
}
}

return false;
}

// Function to start Knight's Tour

vector<vector<int>> knightTour(int n) {
vector<vector<int>> board(n, vector<int>(n, -1));

// Start from top-left corner

board[0][0] = 0;

if (knightTourUtil(0, 0, 1, n, board)) {
return board;
}

return {{-1}};
}

int main() {
int n = 5;

vector<vector<int>> res = knightTour(n);

for (auto &row : res) {

for (int val : row) {
cout << val << " ";
}
cout << endl;
}

return 0;
}

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

[Approach -2] Using Warnsdorff's Algorithm - O(n 3)

Time and O(n2) Space
When solving the Knight's Tour problem, backtracking works but
is inefficient because it explores many unnecessary paths. If the
correct move happens to be the last option, the algorithm
wastes time trying all the wrong ones first.
A smarter strategy is Warnsdorff’s Algorithm , which uses a
heuristic to reduce backtracking. Instead of trying moves in
random order, it always chooses the next move with the fewest
onward moves (the cell with the smallest degree). This prevents
the knight from getting stuck early and greatly improves
efficiency.
Illustration

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

// Define 8 knight moves globally

int dir[8][2] = {
{2, 1}, {1, 2}, {-1, 2}, {-2, 1},
{-2, -1}, {-1, -2}, {1, -2}, {2, -1}
};

// Count the number of onward moves from position (x, y)

int countOptions(vector<vector<int>>& board, int x, int y) {
int count = 0;
 int n = [Link]();

for (int i = 0; i < 8; i++) {

int nx = x + dir[i][0];
int ny = y + dir[i][1];
if (nx >= 0 && ny >= 0 && nx < n && ny < n && board[nx][ny] == -
1) {
count++;
}
}
return count;
}

// Generate valid knight moves from (x, y), sorted by fewest onward
moves
vector<vector<int>> getSortedMoves(vector<vector<int>>& board, int
x, int y) {
vector<vector<int>> moveList;

for (int i = 0; i < 8; i++) {

int nx = x + dir[i][0];
int ny = y + dir[i][1];

if (nx >= 0 && ny >= 0 && nx < [Link]() && ny < [Link]()
&&
board[nx][ny] == -1) {
int options = countOptions(board, nx, ny);
moveList.push_back({options, i});
}
}

// Sort using default vector<int> lexicographic comparison

sort([Link](), [Link]());

return moveList;
}

// Recursive function to solve the Knight's Tour

bool knightTourUtil(int x, int y, int step, int n, vector<vector<int>>&
board) {
if (step == n * n) return true;

vector<vector<int>> moves = getSortedMoves(board, x, y);

for (vector<int> move : moves) {

int dirIdx = move[1];
int nx = x + dir[dirIdx][0];
int ny = y + dir[dirIdx][1];
 board[nx][ny] = step;
if (knightTourUtil(nx, ny, step + 1, n, board))
return true;

// Backtrack
board[nx][ny] = -1;
}
return false;
}

// Function to start Knight's Tour

vector<vector<int>> knightTour(int n) {
vector<vector<int>> board(n, vector<int>(n, -1));

// Start from top-left corner

board[0][0] = 0;

if (knightTourUtil(0, 0, 1, n, board)) {
return board;
}

return {{-1}};
}

int main() {
int n = 5;
vector<vector<int>> result = knightTour(n);

for (vector<int> row : result) {

for (int val : row) {
cout << val << " ";
}
cout << endl;
}

return 0;
}

Output
0 21 10 15 6
11 16 7 20 9
24 1 22 5 14
17 12 3 8 19
2 23 18 13 4
10. Given an integer array arr[], divide it into two subsets such
that the absolute difference between their sums is zero (i.e.,
both subsets have the same sum).
 If the size of the array is even, each subset must contain
exactly n/2 elements.
 If the size of the array is odd, then one subset must contain
n/2 elements and the other must contain (n+1)/2 elements.
Note: It is always guaranteed that the array can be divided into
two such subsets.
Examples:
Input: arr[] = [1, 2, 3, 4]
Output: [[1, 4], [2, 3]]
Explanation: The absolute difference between the sum of both
subsets is 0
Input: arr[] = [5, 10, 15]
Output: [[5, 10], [15]]
Explanation: The absolute difference between the sum of both
subsets is 0
[Approach] Using Recursion and Backtracking -
O(2n) Time and O(n) Space
The idea is to reduce the partitioning problem into finding one
subset of required size whose sum equals half of the total sum.
The other subset is simply the remaining elements.
How to find the subset whose sum is equals to half of
total sum?
First calculate the total sum of the array. Since equal division is
guaranteed, the sum must be even, and the target for each
subset is totalSum / 2.
Then, recursively search for one subset of size n/2 (n/2 or n/2+1
if n is odd) whose sum equals the target.
At each step, we either include the current element in the subset
or skip it.
When the subset reaches required size and sum, we stop and
store the result.

#include <iostream>
#include <vector>

using namespace std;

// Recursive function to find a subset with sum = total/2

bool findSubset(vector<int>& arr, int i, int target,int total,
vector<int>& result) {
int n = [Link]();

if (target == total/2 &&

((n % 2 == 0 && [Link]() == n / 2) ||
(n % 2 != 0 && ([Link]() == n / 2 || [Link]() == n / 2 + 1))))
{

return true;
}

if (i >= n) return false;

// include current element

result.push_back(i);

if(findSubset(arr, i + 1, target + arr[i], total, result)){

return true;
}

// Backtrack
result.pop_back();

// exclude current element

if(findSubset(arr, i + 1, target, total, result)){
return true;
}

return false;
}

vector<vector<int>> equalPartition(vector<int>& arr) {

int n = [Link]();
int total = 0;
for (int x : arr) total += x;

int target = 0;
vector<int> result;

vector<vector<int>> res(2);

// Storing result if possible

if(findSubset(arr, 0, target, total, result)) {

int k = 0;
for (int i = 0; i < n; i++) {
if (k < [Link]() && i == result[k]) {
res[0].push_back(arr[i]);
k++;
 }
else res[1].push_back(arr[i]);
}
}

return res;
}

int main() {
vector<int> arr = {1, 2, 3,4};
vector<vector<int>> res = equalPartition(arr);

for (auto& subset : res) {

for (int x : subset) cout << x << " ";
cout << "\n";
}
}

Output
2 3
1 4

11. Given a 2D binary matrix mat[][] where 0 represents a

landmine and 1 represents a safe cell, find the length of
the shortest safe route from any cell in the first column to any
cell in the last column.
You can move only up, down, left, or right, and can enter only
safe cells (cells that are neither landmines nor adjacent to a
landmine). If there is no safe path to reach the last column,
return -1.
Examples:
Input: mat[][] = [ [1, 0, 1, 1, 1],
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1],
[1, 1, 1, 0, 1],
[1, 1, 1, 1, 0] ]
Output: 6
Explanation: The shortest safe path starts from the first column
(row 2, column 0) and reaches the last column (row 1, column 4)
with length 6.
Input: mat[][] = [ [1, 1, 1, 1, 1],
[1, 1, 0, 1, 1],
[1, 1, 1, 1, 1] ]
Output: -1
Explanation: There is no possible path from first column to last
column.
Table of Content
 [Naive Approach] Using Backtracking - O(4^(n*m)) Time
and O(n*m) Space
 [Expected Approach] Using Breadth-First Search - O(n*m)
Time and O(n*m) Space
[Naive Approach] Using Backtracking - O(4 (n*m))
Time and O(n*m) Space
The idea is to use Backtracking. We first mark all adjacent cells
of the landmines as unsafe. Then for each safe cell of first
column of the matrix, we move forward in all allowed directions
and recursively checks if they leads to the destination or not. If
destination is found, we update the value of shortest path else if
none of the above solutions work we return false from our
function.

↔
// Function to mark unsafe cells (landmines and their adjacent cells)
void markUnsafeCells(vector<vector<int>> &mat) {
int r = [Link]();
int c = mat[0].size();
 // Directions for adjacent cells: up, down, left, right
int row[] = {-1, 1, 0, 0};
int col[] = {0, 0, -1, 1};

vector<vector<int>> temp = mat;

// Mark adjacent cells of landmines (0) as unsafe (0)

for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (temp[i][j] == 0) {
for (int k = 0; k < 4; k++) {
int ni = i + row[k];
int nj = j + col[k];
if (ni >= 0 && ni < r && nj >= 0 && nj < c) {
mat[ni][nj] = 0;
}
}
}
}
}
}

// DFS to find shortest path from (i, j) to any cell in last column
int dfs(vector<vector<int>> &mat, vector<vector<bool>> &visited,
int i, int j, int c) {
int r = [Link]();

if (i < 0 || i >= r || j < 0 || j >= c || mat[i][j] == 0 || visited[i][j]) {

return INT_MAX;
}

if (j == c - 1) {
return 1;
}

visited[i][j] = true;

// Four possible moves: up, down, left, right

int row[] = {-1, 1, 0, 0};
int col[] = {0, 0, -1, 1};

int minPath = INT_MAX;

// Try all four directions

for (int k = 0; k < 4; k++) {
int ni = i + row[k];
int nj = j + col[k];
 int pathLength = dfs(mat, visited, ni, nj, c);
if (pathLength != INT_MAX) {
minPath = min(minPath, 1 + pathLength);
}
}

// Backtrack - unmark current cell

visited[i][j] = false;

return minPath;
}

int shortestPath(vector<vector<int>> &mat) {

int r = [Link]();
int c = mat[0].size();

// Mark all adjacent cells of landmines as unsafe

markUnsafeCells(mat);

// Initialize visited array

vector<vector<bool>> visited(r, vector<bool>(c, false));

int minPath = INT_MAX;

// Try starting from each safe cell in the first column

for (int i = 0; i < r; i++) {
if (mat[i][0] == 1) {
int pathLength = dfs(mat, visited, i, 0, c);
if (pathLength != INT_MAX) {
minPath = min(minPath, pathLength);
}
}
}

return minPath == INT_MAX ? -1 : minPath;

}
↔

Output
6

[Expected Approach] Using Breadth First Search -

O(n*m) Time and O(n*m) Space
The idea is to use BFS to find the shortest safe path from any cell
in the first column to the last column in a binary matrix. BFS is
ideal here because it explores cells level by level, so the first
time we reach a cell in the last column, we are guaranteed that it
is via the shortest path.
For each cell we visit, we check if it is safe by ensuring it is not a
landmine and none of its four neighbors is a landmine. Safe cells
are added to the queue with their current distance, and we mark
them visited directly in the matrix to avoid revisiting. BFS
continues until a last-column cell is reached, returning its
distance, or returns -1 if no safe path exists.

↔
// Check if a cell (i,j) is safe to step on
bool isSafe(vector<vector<int>> &mat, int i, int j) {
int r = [Link]();
int c = mat[0].size();

// cell itself is a landmine or visited

if (mat[i][j] != 1) return false;

// Check all four neighbors

int rowDir[] = {-1, 1, 0, 0};
int colDir[] = {0, 0, -1, 1};

for (int k = 0; k < 4; k++) {

int ni = i + rowDir[k];
int nj = j + colDir[k];
if (ni >= 0 && ni < r && nj >= 0 && nj < c && mat[ni][nj] == 0)

// adjacent to a landmine
return false;
}

return true;
}

// function to find shortest safe path from first column to last column
int shortestPath(vector<vector<int>> &mat) {
int r = [Link]();
int c = mat[0].size();

int rowDir[] = {-1, 1, 0, 0};

int colDir[] = {0, 0, -1, 1};

// {i, j, distance}
queue<array<int,3>> q;

// Enqueue all safe cells in the first column

for (int i = 0; i < r; i++) {
 if (isSafe(mat, i, 0)) {
[Link]({i, 0, 1});

// mark visited
mat[i][0] = -1;
}
}

while (![Link]()) {
auto front = [Link]();
[Link]();
int i = front[0];
int j = front[1];
int dist = front[2];

// Reached last column

if (j == c - 1) return dist;

// Explore four directions

for (int k = 0; k < 4; k++) {
int ni = i + rowDir[k];
int nj = j + colDir[k];

if (ni >= 0 && ni < r && nj >= 0 && nj < c && isSafe(mat, ni, nj)) {
[Link]({ni, nj, dist + 1});

// mark visited
mat[ni][nj] = -1;
}
}
}

// no path found
return -1;
}
↔

Output
6

12. Given an array arr[] of distinct integers and a target, your

task is to find all unique combinations in the array where the
sum is equal to target. The same number may be chosen from the
array any number of times to make target.

Note: You can return your answer in any order, but the driver
code will print the combinations in sorted order only.
Examples:

Input: arr[] = [1, 2, 3], target = 5

Output: [[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 3], [1,
2, 2], [2, 3]]
Explanation: All the combination have sum of elements
equals to target.
Input: arr[] = [2, 4], target = 1
Output: []
Explanation: No combination exits whose sum is equals
to target.
Constraints:
1 ≤ [Link]() ≤ 30
1 ≤ arr[i] ≤ 40
1 ≤ target ≤ 40

13. Given a number k and string s of digits denoting a positive

integer, build the largest number possible by performing swap
operations on the digits of s at most k times.

Examples :

Input: s = "1234567", k = 4
Output: 7654321
Explanation: Three swaps can make the input 1234567 to
7654321, swapping 1 with 7, 2 with 6 and finally 3 with
5.
Input: s = "3435335", k = 3
Output: 5543333
Explanation: Three swaps can make the input 3435335 to
5543333, swapping 3 with 5, 4 with 5 and finally 3 with
4.
Input: s = "1034", k = 2
Output: 4301
Explanation: Two swaps can make the input 1034 to 4301,
swapping 1 with 4 and finally 0 with 3.
Constraints:
1 ≤ [Link]() ≤ 15
1≤k≤7
14. Given a string s, which may contain duplicate characters,
your task is to generate and return an array of
all unique permutations of the string. You can return your
answer in any order.

Examples:

Input: s = "ABC"
Output: ["ABC", "ACB", "BAC", "BCA", "CAB", "CBA"]
Explanation: Given string ABC has 6 unique
permutations.
Input: s = "ABSG"
Output: ["ABGS", "ABSG", "AGBS", "AGSB", "ASBG",
"ASGB", "BAGS", "BASG", "BGAS", "BGSA", "BSAG",
"BSGA", "GABS", "GASB", "GBAS", "GBSA", "GSAB",
"GSBA", "SABG", "SAGB", "SBAG", "SBGA", "SGAB",
"SGBA"]
Explanation: Given string ABSG has 24 unique
permutations.
Input: s = "AAA"
Output: ["AAA"]
Explanation: No other unique permutations can be formed as
all the characters are same.
Constraints:
1 <= [Link]() <= 9
s contains only Uppercase english alphabets

15. Given an undirected graph represented by the edgeList[]

[], where each edgeList[i] contains three integers [u, v, w],
representing an undirected edge from u to v, having
distance w. You are also given a source vertex, and a positive
integer k. Your task is to determine if there exist a simple path
(without any cycle) starting from the source vertex and ending
at any other vertex such that the total weight of the path is at
least k.
Examples:
Input: source = 0, k = 58
edgeList[][] = [[0, 1, 4], [0, 7, 8], [1, 7, 11], [1, 2, 8], [2, 8, 2], [8,
6, 6], [6, 7, 1], [7, 8, 7], [2, 3, 7], [2, 5, 4], [5, 6, 2], [3, 5, 14], [3,
4, 9], [4, 5, 10]]
Output: Yes
Explanation: There exists a simple path 0 -> 7 -> 1 -> 2 -> 8 -
> 6 -> 5 -> 3 -> 4, which has a total distance of 60 which is
more than 58.
Input: source = 0, k = 62
edgeList[][] = [[0, 1, 4], [0, 7, 8], [1, 7, 11], [1, 2, 8], [2, 8, 2], [8,
6, 6], [6, 7, 1], [7, 8, 7], [2, 3, 7], [2, 5, 4], [5, 6, 2], [3, 5, 14], [3,
4, 9], [4, 5, 10]]
Output: No
Explanation: In the above given graph, the longest simple path
has distance 61 (0 -> 7 -> 1-> 2 -> 3 -> 4 -> 5-> 6 -> 8), so
output should be false for any input greater than 61.
Note : The normal greedy approach of picking the longest
weight edge would not work because a shorter edge might lead
to a longer path.
Using Depth First Search and Backtracking - O(V!)
Time and O(V) Space
The idea is to use backtracking to explore every simple path
from the source, keeping track of the remaining weight threshold
at each step. We represent the graph with an adjacency list ( adj)
built from edgeList. Starting from src with target sum k, we
recursively visit unvisited neighbors, subtracting the edge
weight (w) from the remaining k. If at any point k becomes zero
or negative, we’ve found a path whose total weight exceeds the
original threshold. To ensure the path remains simple (no
cycles), we maintain a visited map: before descending into a
neighbor we mark it visited, and after returning we unmark it
(backtrack).
Follow the below given steps:
 Build the adjacency list adj[][] from edgeList, adding both
directions for each undirected edge.
 Initialize visited as an empty map and set visited[src] = 1
 Call findPath(adj, src, k, visited)
 In findPath:
o If k <= 0, return true
o For each (v, w) in adj[src]:
o If visited[v] == 1, skip this neighbor
o Mark visited[v] = 1
o Recursively call findPath(adj, v, k - w,
visited)
If it returns true,
o
propagate true upward
o Backtrack by setting visited[v] = 0
o If no neighbor yields a valid path, return false
 In pathMoreThanK, return the result of findPath to indicate
whether any simple path from src has total weight more than k
Below is given the implementation:

#include <bits/stdc++.h>
using namespace std;

// recursive function to find if there

// exist simple path with weight more than k
bool findPath(unordered_map<int, vector<pair<int, int>>> &adj,
int src, int k, unordered_map<int, int> &visited) {

// if k is 0 or negative, return true

if (k <= 0) return true;

for(auto i: adj[src]) {

// adjacnet vertex and weight of edge

int v = [Link], w = [Link];

// if vertex v is visited, continue

if (visited[v] == 1) continue;

// else include the vertex in path

visited[v] = 1;

// if path greater than k is found, return true

if(findPath(adj, v, k - w, visited))
return true;

// backtrack
visited[v] = 0;
 }

return false;
}

bool pathMoreThanK(vector<vector<int>> &edgeList, int src, int k) {

// create an adjacency list representation of the

// graph
unordered_map<int, vector<pair<int, int>>> adj;
for (const auto &edge : edgeList) {
int u = edge[0], v = edge[1], w = edge[2];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}

// to mark the visited vertices

unordered_map<int,int> visited;

// mark source vertex visited

visited[src] = 1;

return findPath(adj, src, k, visited);

}

int main() {
vector<vector<int>> edgeList = {
{0, 1, 4}, {0, 7, 8}, {1, 7, 11},
{1, 2, 8}, {2, 8, 2}, {8, 6, 6},
{6, 7, 1}, {7, 8, 7}, {2, 3, 7},
{2, 5, 4}, {5, 6, 2}, {3, 5, 14},
{3, 4, 9}, {4, 5, 10}
};
int source = 0, k = 58;
if(pathMoreThanK(edgeList, source, k))
cout << "Yes";
else cout << "No";
return 0;
}

Output
Yes
Time Complexity: O(V!), where V is the number of vertices in
the graph. In the worst case—when the graph is complete—you’ll
explore every simple path starting from the source and visiting
all other V - 1 vertices. There are (V−1)∗(V−2)∗...∗1=(V−1)!
(V−1)∗(V−2)∗...∗1=(V−1)! such paths.
Space Complexity: O(V)

16. Given a 2D binary matrix mat[][] where 0 represent hurdle

and 1 free cell. Find the length of the longest path from a
source (xs, ys) to a destination (xd, yd) with these rules:
 Move only up, down, left, or right (no diagonals).
 Each cell can be visited at most once in a path.
 If reaching the destination is impossible, return -1.
Examples:
Input: xs = 0, ys = 0, xd = 1, yd = 7
mat[][] = [ [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 0, 1, 1, 0, 1, 1, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]
Output: 24
Explanation:

Input: xs = 0, ys = 3, xd = 2, yd = 2
mat[][] =[ [1, 0, 0, 1, 0],
[0, 0, 0, 1, 0],
[0, 1, 1, 0, 0]]
Output: -1
Explanation: We can see that it is impossible to reach the cell
(2,2) from (0,3).
Table of Content
 [Approach] Using Backtracking with Visited Matrix -
O(4^(m*n)) Time and O(m*n) Space
 [Optimized Approach] Without Using Extra Space -
O(4^(m*n)) Time and O(1) Space
[Approach] Using Backtracking with Visited Matrix -
O(4(m*n)) Time and O(m*n) Space
The idea is to use backtracking. We start from the source cell
and recursively explore all four allowed directions—up, down,
left, and right while keeping track of the cells already visited
using a visited array. For each move, we mark the current cell as
visited and continue exploring valid adjacent cells. If we reach
the destination, we update the length of the longest path found
so far. After exploring a path, we backtrack by unmarking the
cell in the visited array so it can be used in other paths.

↔
// Function to find the longest path using backtracking
int dfs(vector<vector<int>> &mat,
vector<vector<bool>> &visited, int i,
int j, int x, int y) {
int m = [Link]();
int n = mat[0].size();

// If destination is reached
if (i == x && j == y) {
return 0;
}

// If cell is invalid, blocked, or already visited

if (i < 0 || i >= m || j < 0 || j >= n ||
mat[i][j] == 0 || visited[i][j]) {
return -1;
}

// Mark current cell as visited

visited[i][j] = true;

int maxPath = -1;

// Four possible moves: up, down, left, right

int row[] = {-1, 1, 0, 0};
int col[] = {0, 0, -1, 1};

for (int k = 0; k < 4; k++) {

int ni = i + row[k];
int nj = j + col[k];

int pathLength = dfs(mat, visited,

ni, nj, x, y);

// If a valid path is found from this direction

 if (pathLength != -1) {
maxPath = max(maxPath, 1 + pathLength);
}
}

// Backtrack - unmark current cell

visited[i][j] = false;

return maxPath;
}

int longestPath(vector<vector<int>> &mat,

int xs, int ys, int xd, int yd) {
int m = [Link]();
int n = mat[0].size();

// Check if source or destination is blocked

if (mat[xs][ys] == 0 || mat[xd][yd] == 0) {
return -1;
}

vector<vector<bool>> visited(m, vector<bool>(n, false));

return dfs(mat, visited, xs, ys, xd, yd);
}
↔

Output
24

[Optimized Approach] Without Using Extra Space -

O(4(m*n)) Time and O(1) Space
Instead of using a separate visited matrix, mark cells as visited
directly in the input matrix by setting them to 0. Explore all four
directions recursively. After finishing a path from a cell, restore
its value to 1 (backtracking).

↔
// Function to find the longest path using backtracking without extra space
int dfs(vector<vector<int>> &mat, int i, int j, int x, int y) {
int m = [Link]();
int n = mat[0].size();

// If destination is reached
if (i == x && j == y) {
return 0;
 }

// If cell is invalid or blocked (0 means blocked or visited)

if (i < 0 || i >= m || j < 0 || j >= n || mat[i][j] == 0) {
return -1;
}

// Mark current cell as visited by temporarily setting it to 0

mat[i][j] = 0;

int maxPath = -1;

// Four possible moves: up, down, left, right

int row[] = {-1, 1, 0, 0};
int col[] = {0, 0, -1, 1};

for (int k = 0; k < 4; k++) {

int ni = i + row[k];
int nj = j + col[k];

int pathLength = dfs(mat, ni, nj, x, y);

// If a valid path is found from this direction

if (pathLength != -1) {
maxPath = max(maxPath, 1 + pathLength);
}
}

// Backtrack - restore the cell's original value (1)

mat[i][j] = 1;

return maxPath;
}

int longestPath(vector<vector<int>> &mat, int xs, int ys, int xd, int yd) {
int m = [Link]();
int n = mat[0].size();

// Check if source or destination is blocked

if (mat[xs][ys] == 0 || mat[xd][yd] == 0) {
return -1;
}

return dfs(mat, xs, ys, xd, yd);

}
↔

Output
24
17. Given a 2D matrix of dimension m✕n, the task is to print all
the possible paths from the top left corner to the bottom
right corner in a 2D matrix with the constraints that from each
cell you can either move to right or down only.
Examples :
Input: [[1,2,3],
[4,5,6]]
Output: [[1,4,5,6],
[1,2,5,6],
[1,2,3,6]]
Input: [[1,2],
[3,4]]
Output: [[1,2,4],
[1,3,4]]
Print all possible paths from top left to bottom right in matrix
using Backtracking
Explore all the possible paths from a current cell using
recursion and backtracking to reach bottom right cell.
 Base cases: Check If the bottom right cell, print the
current path.
 Boundary cases: In case in we reach out of the matrix,
return from it.
 Otherwise, Include the current cell in the path
 Make two recursive call:
o Move right in the matrix
o Move down in the matrix
 Backtrack: Remove the current cell from the current path
Implementation of the above approach:

#include <bits/stdc++.h>
using namespace std;

// To store the matrix dimension

int M, N;

// Function to print the path taken to reach destination

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

// Function to find all possible path in matrix from top

// left cell to bottom right cell
void findPaths(vector<vector<int> >& arr, vector<int>& path,
int i, int j)
{

// if the bottom right cell, print the path

if (i == M - 1 && j == N - 1) {
path.push_back(arr[i][j]);
printPath(path);
path.pop_back();
return;
}

// Boundary cases: In case in we reach out of the matrix

if (i < 0 || i >= M || j < 0 || j >= N) {
return;
}

// Include the current cell in the path

path.push_back(arr[i][j]);

// Move right in the matrix

if (j + 1 < N) {
findPaths(arr, path, i, j + 1);
}

// Move down in the matrix

if (i + 1 < M) {
findPaths(arr, path, i + 1, j);
}

// Backtrack: Remove the current cell from the current

// path
path.pop_back();
}

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

// To store the path

 vector<int> path;

// Starting cell `(0, 0)` cell

int i = 0, j = 0;

M = [Link]();
N = arr[0].size();

// Function call
findPaths(arr, path, i, j);

return 0;
}

Output
1, 2, 3, 6, 9,
1, 2, 5, 6, 9,
1, 2, 5, 8, 9,
1, 4, 5, 6, 9,
1, 4, 5, 8, 9,
1, 4, 7, 8, 9,
Time Complexity : O(2^(N*M))
Auxiliary space : O(N + M), where M and N are dimension of
matrix.

18. Given an integer array arr[ ] and an integer k, the task is to

check if the array arr[ ] could be divided into k non-empty
subsets with equal sum of elements.
Note: All elements of this array should be part of exactly one
partition.

Examples:

Input: arr[] = [2, 1, 4, 5, 6], k = 3

Output: true
Explanation: We can divide above array into 3 parts
with equal sum as (2, 4), (1, 5), (6)
Input: arr[] = [2, 1, 5, 5, 6], k = 3
Output: false
Explanation: It is not possible to divide above array
into 3 parts with equal sum.
Constraints:
1 ≤ k ≤ [Link]() ≤ 10
1 ≤ arr[i] ≤ 100

19. Given two integers N and K, find the Kth permutation

sequence of numbers from 1 to N without using STL function.
Note: Assume that the inputs are such that Kth permutation of N
number is always possible.
Examples:
Input: N = 3, K = 4
Output: 231
Explanation:
The ordered list of permutation sequence from integer 1 to 3 is :
123, 132, 213, 231, 312, 321. So, the 4th permutation sequence
is "231".
Input: N = 2, K = 1
Output: 12
Explanation:
For n = 2, only 2 permutations are possible 12 21. So, the 1st
permutation sequence is "12".
Naive Approach:
To solve the problem mentioned above the simple approach is to
find all permutation sequences and output the kth out of them.
But this method is not so efficient and takes more time, hence it
can be optimized.

// C++ program to Find the kth Permutation

// Sequence of first n natural numbers
#include <bits/stdc++.h>
using namespace std;

// recursive function to generate all

// possible permutations of a string
void generate_permutations(string& str, int idx, vector<string>& result) {
// base case
if (idx == [Link]()) {
result.push_back(str);
return;
}

// traverse string from idx to end

for (int i = idx; i < [Link](); i++) {
 swap(str[i], str[idx]);
generate_permutations(str, idx + 1, result);
swap(str[i], str[idx]);
}
}

// Function to find the

// kth permutation of n numbers
string findKthPermutation(int n, int k) {
string str = "";
vector<string> result;

// Insert all natural number

// upto n in string
for (int i = 1; i <= n; i++) {
str.push_back(i + '0');
}

generate_permutations(str, 0, result);
// sort the generated permutations
sort([Link](), [Link]());

// make k 0-based indexed to point to kth sequence

return result[k-1];
}

// Driver code
int main() {
int n = 3, k = 4;

// function call
string kth_perm_seq = findKthPermutation(n, k);
cout << kth_perm_seq << endl;

return 0;
}

// This code is contributed by Tapesh(tapeshdua420)

Output
231
Time Complexity = O((N! * N) + (N! * log N!))
Auxiliary Space = O(N) to store all permutations
[ Expected Approach 1 ]
The first position of an n length sequence is occupied by each of
the numbers from 1 to n exactly n! / n that is (n-1)! number of
times and in ascending order. So the first position of the kth
sequence will be occupied by the number present at index = k /
(n-1)! (according to 1-based indexing).
 The currently found number can not occur again so it is
removed from the original n numbers and now the problem
reduces to finding the ( k % (n-1)! )th permutation sequence
of the remaining n-1 numbers.
 This process can be repeated until we have only one number
left which will be placed in the first position of the last 1-
length sequence.
 The factorial values involved here can be very large as
compared to k. So, the trick used to avoid the full computation
of such large factorials is that as soon as the product n * (n-
1) * ... becomes greater than k, we no longer need to find
the actual factorial value because:
k / n_actual_factorial_value = 0
and k / n_partial_factorial_value = 0
when partial_factorial_value > k

Below is the implementation of the above approach:

// C++ program to Find the kth Permutation

// Sequence of first n natural numbers

#include <bits/stdc++.h>
using namespace std;

// Function to find the index of number

// at first position of
// kth sequence of set of size n
int findFirstNumIndex(int& k, int n)
{

if (n == 1)
return 0;
n--;

int first_num_index;
// n_actual_fact = n!
int n_partial_fact = n;

while (k >= n_partial_fact

&& n > 1) {
n_partial_fact
 = n_partial_fact
* (n - 1);
n--;
}

// First position of the

// kth sequence will be
// occupied by the number present
// at index = k / (n-1)!
first_num_index = k / n_partial_fact;

k = k % n_partial_fact;

return first_num_index;
}

// Function to find the

// kth permutation of n numbers
string findKthPermutation(int n, int k)
{
// Store final answer
string ans = "";

set<int> s;

// Insert all natural number

// upto n in set
for (int i = 1; i <= n; i++)
[Link](i);

set<int>::iterator itr;

// Mark the first position

itr = [Link]();

// subtract 1 to get 0 based indexing

k = k - 1;

for (int i = 0; i < n; i++) {

int index
= findFirstNumIndex(k, n - i);

advance(itr, index);

// itr now points to the

// number at index in set s
ans += (to_string(*itr));
 // remove current number from the set
[Link](itr);

itr = [Link]();
}
return ans;
}

// Driver code
int main()
{

int n = 3, k = 4;

string kth_perm_seq
= findKthPermutation(n, k);

cout << kth_perm_seq << endl;

return 0;
}

Output
231
Time Complexity : O(N^2)
Auxiliary Space : O(N)
[Expected Approach 2] Using Combinatorics
The base idea is that the first character can be found knowing
that it has repeated (n-1)! times, given a particular value of n.
For example, given the base case "1234" with n = 4, we can list
out all the permutations that starts with '1':
1234
1324
1342
1243
1423
1432
As we can see, there are 6 cases in total where we have n = 4
that starts with '1'. That is because there are exactly (n-1)! = (4-
1)! = 3! = 6 unique cases with the characters after the first one.
With this knowledge, we can deal with the problem recursively:
Given a particular value of n, and k, we can compute the first
character in the set (i.e., {1,2,3,4,...,n}) of characters in
increasing order by:
pos = k / factorial(n-1)
where pos is the index to the character in the set we want.
Then we have to remove the character at index pos from the set,
since we can only use each character once.
What about the next iteration? Now that we have the desired
character for n, we can turn to n-1, since we have knocked one
of the n characters down, so n-1 left to go.
But what about k? Well, since we have considered a total number
of k * factorial(n-1) permutations, we are left with k %=
factorial(n-1), and that is going to be our new k for the next
iteration.
An example for this, back to our case of n=4 above, imagine we
have input k = 21. Now, we have already established there are 6
unique cases for the remaining n-1 characters for EACH of the
unique character for the first one:
Looking at first character:
1 ... (6 permutations)
2 ... (6 permutations)
3 ... (6 permutations)
Figured out first character is '4'.
Figured out first character, moving onto second characters, we
have already considered 18 cases, so left with k %= factorial(n-
1) = 21 %= 6 = 3 left.

// C++ program to Find the kth Permutation

// Sequence of first n natural numbers

#include <bits/stdc++.h>
using namespace std;

// Function to find the index of number

// at first position of
// kth sequence of set of size n
// percalculated factorials
int fact[10] = {1,1,2,6,24,120,720,5040,40320,362880};

// recursively insert numbers in to string

void permutation(int n, int k, set<int>&nums, string &str)
{
// base case n==0 then no numbers to process
if(n==0) return;

int val;

// base case k=1 then add numbers from begin

 // base case k=0 then next numbers to be added will be in reverse
from rbegin
// k<=fact[n-1] then add the begin number
if(k<=1 || k<=fact[n-1])
{
val = k==0 ? *[Link]() : *[Link]();
}
else
{
// calculate number of values cover k => k/fact[n-1]
// so next value index => k/fact[n-1]
int index = k/fact[n-1];
k = k %fact[n-1]; // remaining permutations

// also if k%fact[n-1] == 0 then kth permutation covered by value

is in index-1
// EX: [2,3] n=2, k=2 => index = k/fact[n-1] = 2/1 = 2
// as k%fact[n-1] => 2%1 = 0, so decrease index to 1
// so we take the value 3 as next value

if(k==0)index--;

// value taken
val = *next([Link](),index);
}

// add value to the string and remove from set

str+= to_string(val);
[Link](val);

// decrement n in each step

return permutation(n-1,k,nums,str);
}

string getPermutation(int n, int k) {

// insert numbers 1 to N in to set

set<int>nums;
for(int i=1;i<=n;i++)[Link](i);

// resulting string
string str = "";

permutation(n,k,nums,str);

return str;
}

// Driver code
int main()
{

int n = 3, k = 4;

string kth_perm_seq
= getPermutation(n, k);

cout << kth_perm_seq << endl;

return 0;
}
Output:
231
Time Complexity : O(N * N) for generating all the permutations
and traversals.
Auxiliary Space : O(N) for storing all permutation.