15 Backtracking Interview Questions

BY: coding_error1

1. N-Queens Problem
Problem: Place N queens on an N×N chessboard so that no two queens attack each other.

Python Solution
def solve_n_queens(n):
def is_safe(board, row, col):
# Check column
for i in range(row):
if board[i][col] == 1:
return False

# Check diagonal (top-left to bottom-right)

i, j = row - 1, col - 1
while i >= 0 and j >= 0:
if board[i][j] == 1:
return False
i -= 1
j -= 1

# Check diagonal (top-right to bottom-left)

i, j = row - 1, col + 1
while i >= 0 and j < n:
if board[i][j] == 1:
return False
i -= 1
j += 1

return True

def backtrack(board, row):

if row == n:
return True

for col in range(n):

if is_safe(board, row, col):
board[row][col] = 1
if backtrack(board, row + 1):
return True
board[row][col] = 0

return False

board = [[0] * n for _ in range(n)]

if backtrack(board, 0):
return board
return None

BY: coding_error1
# Example usage
result = solve_n_queens(4)
if result:
for row in result:
print(row)

Java Solution
public class NQueens {
public static boolean solveNQueens(int n) {
int[][] board = new int[n][n];
if (backtrack(board, 0, n)) {
printBoard(board, n);
return true;
}
return false;
}

private static boolean isSafe(int[][] board, int row, int col, int n) {
// Check column
for (int i = 0; i < row; i++) {
if (board[i][col] == 1) return false;
}

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

for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {

if (board[i][j] == 1) return false;
}

return true;
}

private static boolean backtrack(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 (backtrack(board, row + 1, n)) return true;
board[row][col] = 0;
}
}
return false;
}

private static void printBoard(int[][] board, int n) {

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(board[i][j] + " ");
}
System.out.println();
}
}
}

C++ Solution
BY: coding_error1
#include <iostream>
#include <vector>
using namespace std;

class NQueens {
public:
bool solveNQueens(int n) {
vector<vector<int>> board(n, vector<int>(n, 0));
if (backtrack(board, 0, n)) {
printBoard(board, n);
return true;
}
return false;
}

private:
bool isSafe(vector<vector<int>>& board, int row, int col, int n) {
// Check column
for (int i = 0; i < row; i++) {
if (board[i][col] == 1) return false;
}

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

for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {

if (board[i][j] == 1) return false;
}

return true;
}

bool backtrack(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 (backtrack(board, row + 1, n)) return true;
board[row][col] = 0;
}
}
return false;
}

void printBoard(vector<vector<int>>& board, int n) {

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

Key Concepts and Patterns

BY: coding_error1
Common Backtracking Template
def backtrack(parameters):
# Base case
if condition_met:
process_solution()
return

# Try all possible choices

for choice in possible_choices:
# Make choice
make_choice(choice)

# Recursively explore
backtrack(updated_parameters)

# Undo choice (backtrack)

undo_choice(choice)

Time Complexity Analysis

• N-Queens: O(N!)
• Sudoku: O(9^(n*n)) where n is empty cells
• Permutations: O(N! × N)
• Subsets: O(2^N × N)
• Combination Sum: O(2^target)

Space Complexity

• Generally O(N) for recursion stack

• Additional space for storing solutions

Optimization Techniques

1. Pruning: Early termination when solution is impossible

2. Constraint Propagation: Reduce search space using constraints
3. Heuristics: Choose better ordering for variables/

2. Sudoku Solver
Problem: Fill a 9×9 Sudoku grid following the standard rules.

Python Solution
def solve_sudoku(board):
def is_valid(board, row, col, num):
# Check row
for j in range(9):
if board[row][j] == num:
return False

# Check column
for i in range(9):

BY: coding_error1
 if board[i][col] == num:
return False

# Check 3x3 box

start_row, start_col = 3 * (row // 3), 3 * (col // 3)
for i in range(start_row, start_row + 3):
for j in range(start_col, start_col + 3):
if board[i][j] == num:
return False

return True

def backtrack():
for i in range(9):
for j in range(9):
if board[i][j] == 0:
for num in range(1, 10):
if is_valid(board, i, j, num):
board[i][j] = num
if backtrack():
return True
board[i][j] = 0
return False
return True

return backtrack()

# Example usage
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]
]

if solve_sudoku(board):
for row in board:
print(row)

Java Solution
public class SudokuSolver {
public static boolean solveSudoku(int[][] board) {
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
if (board[row][col] == 0) {
for (int num = 1; num <= 9; num++) {
if (isValid(board, row, col, num)) {
board[row][col] = num;
if (solveSudoku(board)) return true;
board[row][col] = 0;
}
}
return false;
}

BY: coding_error1
 }
}
return true;
}

private static boolean isValid(int[][] board, int row, int col, int
num) {
// Check row and column
for (int i = 0; i < 9; i++) {
if (board[row][i] == num || board[i][col] == num) return false;
}

// Check 3x3 box

int startRow = 3 * (row / 3);
int startCol = 3 * (col / 3);
for (int i = startRow; i < startRow + 3; i++) {
for (int j = startCol; j < startCol + 3; j++) {
if (board[i][j] == num) return false;
}
}
return true;
}
}

C++ Solution
#include <vector>
using namespace std;

class SudokuSolver {
public:
bool solveSudoku(vector<vector<int>>& board) {
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
if (board[row][col] == 0) {
for (int num = 1; num <= 9; num++) {
if (isValid(board, row, col, num)) {
board[row][col] = num;
if (solveSudoku(board)) return true;
board[row][col] = 0;
}
}
return false;
}
}
}
return true;
}

private:
bool isValid(vector<vector<int>>& board, int row, int col, int num) {
// Check row and column
for (int i = 0; i < 9; i++) {
if (board[row][i] == num || board[i][col] == num) return false;
}

// Check 3x3 box

int startRow = 3 * (row / 3);
int startCol = 3 * (col / 3);
for (int i = startRow; i < startRow + 3; i++) {

BY: coding_error1
 for (int j = startCol; j < startCol + 3; j++) {
if (board[i][j] == num) return false;
}
}
return true;
}
};

3. Generate All Permutations

Problem: Generate all permutations of a given array.

Python Solution
def permutations(nums):
result = []

def backtrack(current):
if len(current) == len(nums):
result.append(current[:])
return

for num in nums:

if num not in current:
current.append(num)
backtrack(current)
current.pop()

backtrack([])
return result

# Example usage
print(permutations([1, 2, 3]))

Java Solution
import java.util.*;

public class Permutations {

public static List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(nums, new ArrayList<>(), result);
return result;
}

private static void backtrack(int[] nums, List<Integer> current,

List<List<Integer>> result) {
if (current.size() == nums.length) {
result.add(new ArrayList<>(current));
return;
}

for (int num : nums) {

if (!current.contains(num)) {
current.add(num);
backtrack(nums, current, result);
current.remove(current.size() - 1);
}

BY: coding_error1
 }
}
}

C++ Solution
#include <vector>
#include <algorithm>
using namespace std;

class Permutations {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
vector<int> current;
backtrack(nums, current, result);
return result;
}

private:
void backtrack(vector<int>& nums, vector<int>& current,
vector<vector<int>>& result) {
if (current.size() == nums.size()) {
result.push_back(current);
return;
}

for (int num : nums) {

if (find(current.begin(), current.end(), num) == current.end())
{
current.push_back(num);
backtrack(nums, current, result);
current.pop_back();
}
}
}
};

4. Combination Sum
Problem: Find all unique combinations where the candidate numbers sum to target.

Python Solution
def combination_sum(candidates, target):
result = []

def backtrack(start, current, remaining):

if remaining == 0:
result.append(current[:])
return

for i in range(start, len(candidates)):

if candidates[i] <= remaining:
current.append(candidates[i])
backtrack(i, current, remaining - candidates[i])
current.pop()

BY: coding_error1
 backtrack(0, [], target)
return result

# Example usage
print(combination_sum([2, 3, 6, 7], 7))

Java Solution
import java.util.*;

public class CombinationSum {

public static List<List<Integer>> combinationSum(int[] candidates, int
target) {
List<List<Integer>> result = new ArrayList<>();
backtrack(candidates, target, 0, new ArrayList<>(), result);
return result;
}

private static void backtrack(int[] candidates, int remaining, int

start,
List<Integer> current, List<List<Integer>>
result) {
if (remaining == 0) {
result.add(new ArrayList<>(current));
return;
}

for (int i = start; i < candidates.length; i++) {

if (candidates[i] <= remaining) {
current.add(candidates[i]);
backtrack(candidates, remaining - candidates[i], i,
current, result);
current.remove(current.size() - 1);
}
}
}
}

C++ Solution
#include <vector>
using namespace std;

class CombinationSum {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target)
{
vector<vector<int>> result;
vector<int> current;
backtrack(candidates, target, 0, current, result);
return result;
}

private:
void backtrack(vector<int>& candidates, int remaining, int start,
vector<int>& current, vector<vector<int>>& result) {
if (remaining == 0) {
result.push_back(current);
return;

BY: coding_error1
 }

for (int i = start; i < candidates.size(); i++) {

if (candidates[i] <= remaining) {
current.push_back(candidates[i]);
backtrack(candidates, remaining - candidates[i], i,
current, result);
current.pop_back();
}
}
}
};

5. Word Search
Problem: Find if a word exists in a 2D board of characters.

Python Solution
def word_search(board, word):
if not board or not board[0]:
return False

rows, cols = len(board), len(board[0])

def backtrack(row, col, index):

if index == len(word):
return True

if (row < 0 or row >= rows or col < 0 or col >= cols or
board[row][col] != word[index]):
return False

# Mark as visited
temp = board[row][col]
board[row][col] = '#'

# Explore all directions

found = (backtrack(row + 1, col, index + 1) or
backtrack(row - 1, col, index + 1) or
backtrack(row, col + 1, index + 1) or
backtrack(row, col - 1, index + 1))

# Restore original value

board[row][col] = temp
return found

for i in range(rows):
for j in range(cols):
if backtrack(i, j, 0):
return True

return False

# Example usage
board = [
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']

BY: coding_error1
]
print(word_search(board, "ABCCED")) # True

Java Solution
public class WordSearch {
public static boolean exist(char[][] board, String word) {
if (board == null || board.length == 0) return false;

int rows = board.length, cols = board[0].length;

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

for (int j = 0; j < cols; j++) {
if (backtrack(board, word, i, j, 0)) return true;
}
}
return false;
}

private static boolean backtrack(char[][] board, String word, int row,

int col, int index) {
if (index == word.length()) return true;

if (row < 0 || row >= board.length || col < 0 || col >=

board[0].length ||
board[row][col] != word.charAt(index)) return false;

char temp = board[row][col];

board[row][col] = '#';

boolean found = backtrack(board, word, row + 1, col, index + 1) ||

backtrack(board, word, row - 1, col, index + 1) ||
backtrack(board, word, row, col + 1, index + 1) ||
backtrack(board, word, row, col - 1, index + 1);

board[row][col] = temp;
return found;
}
}

C++ Solution
#include <vector>
#include <string>
using namespace std;

class WordSearch {
public:
bool exist(vector<vector<char>>& board, string word) {
if (board.empty()) return false;

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

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

for (int j = 0; j < cols; j++) {
if (backtrack(board, word, i, j, 0)) return true;
}
}
return false;

BY: coding_error1
 }

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

if (row < 0 || row >= board.size() || col < 0 || col >=

board[0].size() ||
board[row][col] != word[index]) return false;

char temp = board[row][col];

board[row][col] = '#';

bool found = backtrack(board, word, row + 1, col, index + 1) ||

backtrack(board, word, row - 1, col, index + 1) ||
backtrack(board, word, row, col + 1, index + 1) ||
backtrack(board, word, row, col - 1, index + 1);

board[row][col] = temp;
return found;
}
};

6. Palindrome Partitioning
Problem: Partition a string such that every substring is a palindrome.

Python Solution
def palindrome_partition(s):
result = []

def is_palindrome(string):
return string == string[::-1]

def backtrack(start, current):

if start == len(s):
result.append(current[:])
return

for end in range(start + 1, len(s) + 1):

substring = s[start:end]
if is_palindrome(substring):
current.append(substring)
backtrack(end, current)
current.pop()

backtrack(0, [])
return result

# Example usage
print(palindrome_partition("aab"))

Java Solution
import java.util.*;

BY: coding_error1
public class PalindromePartition {
public static List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<>();
backtrack(s, 0, new ArrayList<>(), result);
return result;
}

private static void backtrack(String s, int start, List<String>

current,
List<List<String>> result) {
if (start == s.length()) {
result.add(new ArrayList<>(current));
return;
}

for (int end = start + 1; end <= s.length(); end++) {

String substring = s.substring(start, end);
if (isPalindrome(substring)) {
current.add(substring);
backtrack(s, end, current, result);
current.remove(current.size() - 1);
}
}
}

private static boolean isPalindrome(String s) {

int left = 0, right = s.length() - 1;
while (left < right) {
if (s.charAt(left++) != s.charAt(right--)) return false;
}
return true;
}
}

C++ Solution
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class PalindromePartition {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> result;
vector<string> current;
backtrack(s, 0, current, result);
return result;
}

private:
void backtrack(string& s, int start, vector<string>& current,
vector<vector<string>>& result) {
if (start == s.length()) {
result.push_back(current);
return;
}

for (int end = start + 1; end <= s.length(); end++) {

string substring = s.substr(start, end - start);

BY: coding_error1
 if (isPalindrome(substring)) {
current.push_back(substring);
backtrack(s, end, current, result);
current.pop_back();
}
}
}

bool isPalindrome(string& s) {
int left = 0, right = s.length() - 1;
while (left < right) {
if (s[left++] != s[right--]) return false;
}
return true;
}
};

7. Subset Generation
Problem: Generate all possible subsets of a given set.

Python Solution
def subsets(nums):
result = []

def backtrack(start, current):

result.append(current[:])

for i in range(start, len(nums)):

current.append(nums[i])
backtrack(i + 1, current)
current.pop()

backtrack(0, [])
return result

# Example usage
print(subsets([1, 2, 3]))

Java Solution
import java.util.*;

public class Subsets {

public static List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(nums, 0, new ArrayList<>(), result);
return result;
}

private static void backtrack(int[] nums, int start, List<Integer>

current,
List<List<Integer>> result) {
result.add(new ArrayList<>(current));

for (int i = start; i < nums.length; i++) {

current.add(nums[i]);

BY: coding_error1
 backtrack(nums, i + 1, current, result);
current.remove(current.size() - 1);
}
}
}

C++ Solution
#include <vector>
using namespace std;

class Subsets {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> result;
vector<int> current;
backtrack(nums, 0, current, result);
return result;
}

private:
void backtrack(vector<int>& nums, int start, vector<int>& current,
vector<vector<int>>& result) {
result.push_back(current);

for (int i = start; i < nums.size(); i++) {

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

8. Letter Combinations of Phone Number

Problem: Given a digit string, return all possible letter combinations.

Python Solution
def letter_combinations(digits):
if not digits:
return []

phone = {
'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
}

result = []

def backtrack(index, current):

if index == len(digits):
result.append(current)
return

for letter in phone[digits[index]]:

backtrack(index + 1, current + letter)

BY: coding_error1
 backtrack(0, "")
return result

# Example usage
print(letter_combinations("23"))

Java Solution
import java.util.*;

public class LetterCombinations {

private static final String[] PHONE = {
"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
};

public static List<String> letterCombinations(String digits) {

List<String> result = new ArrayList<>();
if (digits.length() == 0) return result;

backtrack(digits, 0, new StringBuilder(), result);

return result;
}

private static void backtrack(String digits, int index, StringBuilder

current,
List<String> result) {
if (index == digits.length()) {
result.add(current.toString());
return;
}

String letters = PHONE[digits.charAt(index) - '0'];

for (char letter : letters.toCharArray()) {
current.append(letter);
backtrack(digits, index + 1, current, result);
current.deleteCharAt(current.length() - 1);
}
}
}

C++ Solution
#include <vector>
#include <string>
using namespace std;

class LetterCombinations {
public:
vector<string> letterCombinations(string digits) {
if (digits.empty()) return {};

vector<string> phone = {"", "", "abc", "def", "ghi", "jkl",

"mno", "pqrs", "tuv", "wxyz"};
vector<string> result;
string current = "";

backtrack(digits, 0, current, result, phone);

return result;
}

BY: coding_error1
private:
void backtrack(string& digits, int index, string& current,
vector<string>& result, vector<string>& phone) {
if (index == digits.length()) {
result.push_back(current);
return;
}

string letters = phone[digits[index] - '0'];

for (char letter : letters) {
current.push_back(letter);
backtrack(digits, index + 1, current, result, phone);
current.pop_back();
}
}
};

9. Rat in a Maze
Problem: Find path for a rat to reach from source to destination in a maze.

Python Solution
def rat_in_maze(maze):
n = len(maze)
solution = [[0] * n for _ in range(n)]

def is_safe(x, y):

return 0 <= x < n and 0 <= y < n and maze[x][y] == 1

def backtrack(x, y):

if x == n - 1 and y == n - 1:
solution[x][y] = 1
return True

if is_safe(x, y):
solution[x][y] = 1

# Move right
if backtrack(x, y + 1):
return True

# Move down
if backtrack(x + 1, y):
return True

# Backtrack
solution[x][y] = 0
return False

return False

if backtrack(0, 0):
return solution
return None

# Example usage
maze = [

BY: coding_error1
 [1, 0, 0, 0],
[1, 1, 0, 1],
[0, 1, 0, 0],
[1, 1, 1, 1]
]
result = rat_in_maze(maze)
if result:
for row in result:
print(row)

Java Solution
public class RatInMaze {
public static boolean solveMaze(int[][] maze) {
int n = maze.length;
int[][] solution = new int[n][n];

if (backtrack(maze, 0, 0, solution, n)) {

printSolution(solution, n);
return true;
}
return false;
}

private static boolean isSafe(int[][] maze, int x, int y, int n) {

return x >= 0 && x < n && y >= 0 && y < n && maze[x][y] == 1;
}

private static boolean backtrack(int[][] maze, int x, int y, int[][]

solution, int n) {
if (x == n - 1 && y == n - 1) {
solution[x][y] = 1;
return true;
}

if (isSafe(maze, x, y, n)) {
solution[x][y] = 1;

// Move right
if (backtrack(maze, x, y + 1, solution, n)) return true;

// Move down
if (backtrack(maze, x + 1, y, solution, n)) return true;

// Backtrack
solution[x][y] = 0;
return false;
}
return false;
}

private static void printSolution(int[][] solution, int n) {

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(solution[i][j] + " ");
}
System.out.println();
}
}
}

BY: coding_error1
C++ Solution
#include <vector>
#include <iostream>
using namespace std;

class RatInMaze {
public:
bool solveMaze(vector<vector<int>>& maze) {
int n = maze.size();
vector<vector<int>> solution(n, vector<int>(n, 0));

if (backtrack(maze, 0, 0, solution, n)) {

printSolution(solution, n);
return true;
}
return false;
}

private:
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 backtrack(vector<vector<int>>& maze, int x, int y,

vector<vector<int>>& solution, int n) {
if (x == n - 1 && y == n - 1) {
solution[x][y] = 1;
return true;
}

if (isSafe(maze, x, y, n)) {
solution[x][y] = 1;

// Move right
if (backtrack(maze, x, y + 1, solution, n)) return true;

// Move down
if (backtrack(maze, x + 1, y, solution, n)) return true;

// Backtrack
solution[x][y] = 0;
return false;
}
return false;
}

void printSolution(vector<vector<int>>& solution, int n) {

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

10. Graph Coloring

BY: coding_error1
Problem: Color the vertices of a graph such that no two adjacent vertices have the same
color.

Python Solution
def graph_coloring(graph, m):
n = len(graph)
colors = [0] * n

def is_safe(vertex, color):

for i in range(n):
if graph[vertex][i] == 1 and colors[i] == color:
return False
return True

def backtrack(vertex):
if vertex == n:
return True

for color in range(1, m + 1):

if is_safe(vertex, color):
colors[vertex] = color
if backtrack(vertex + 1):
return True
colors[vertex] = 0

return False

if backtrack(0):
return colors
return None

# Example usage
graph = [
[0, 1, 1, 1],
[1, 0, 1, 0],
[1, 1, 0, 1],
[1, 0, 1, 0]
]
result = graph_coloring(graph, 3)
print(result) # [1, 2, 3, 2]

Java Solution
public class GraphColoring {
public static boolean graphColoring(int[][] graph, int m) {
int n = graph.length;
int[] colors = new int[n];

if (backtrack(graph, m, colors, 0, n)) {

printColors(colors, n);
return true;
}
return false;
}

private static boolean isSafe(int[][] graph, int vertex, int color,

int[] colors, int n) {
for (int i = 0; i < n; i++) {

BY: coding_error1
 if (graph[vertex][i] == 1 && colors[i] == color) return false;
}
return true;
}

private static boolean backtrack(int[][] graph, int m, int[] colors,

int vertex, int n) {
if (vertex == n) return true;

for (int color = 1; color <= m; color++) {

if (isSafe(graph, vertex, color, colors, n)) {
colors[vertex] = color;
if (backtrack(graph, m, colors, vertex + 1, n)) return
true;
colors[vertex] = 0;
}
}
return false;
}

private static void printColors(int[] colors, int n) {

for (int i = 0; i < n; i++) {
System.out.print(colors[i] + " ");
}
System.out.println();
}
}

C++ Solution
#include <vector>
#include <iostream>
using namespace std;

class GraphColoring {
public:
bool graphColoring(vector<vector<int>>& graph, int m) {
int n = graph.size();
vector<int> colors(n, 0);

if (backtrack(graph, m, colors, 0, n)) {

printColors(colors, n);
return true;
}
return false;
}

private:
bool isSafe(vector<vector<int>>& graph, int vertex, int color,
vector<int>& colors, int n) {
for (int i = 0; i < n; i++) {
if (graph[vertex][i] == 1 && colors[i] == color) return false;
}
return true;
}

bool backtrack(vector<vector<int>>& graph, int m, vector<int>& colors,

int vertex, int n) {
if (vertex == n) return true;

BY: coding_error1
 for (int color = 1; color <= m; color++) {
if (isSafe(graph, vertex, color, colors, n)) {
colors[vertex] = color;
if (backtrack(graph, m, colors, vertex + 1, n)) return
true;
colors[vertex] = 0;
}
}
return false;
}

void printColors(vector<int>& colors, int n) {

for (int i = 0; i < n; i++) {
cout << colors[i] << " ";
}
cout << endl;
}
};

11. Knight's Tour

Problem: Find a sequence of moves for a knight to visit every square on a chessboard exactly
once.

Python Solution
def knights_tour(n):
# Knight moves
moves = [(2, 1), (1, 2), (-1, 2), (-2, 1),
(-2, -1), (-1, -2), (1, -2), (2, -1)]

board = [[-1] * n for _ in range(n)]

def is_safe(x, y):

return 0 <= x < n and 0 <= y < n and board[x][y] == -1

def backtrack(x, y, move_count):

board[x][y] = move_count

if move_count == n * n - 1:
return True

for dx, dy in moves:

next_x, next_y = x + dx, y + dy
if is_safe(next_x, next_y):
if backtrack(next_x, next_y, move_count + 1):
return True

board[x][y] = -1
return False

if backtrack(0, 0, 0):
return board
return None

# Example usage (for small boards)

result = knights_tour(5)
if result:
for row in result:

BY: coding_error1
 print(row)

Java Solution
public class KnightsTour {
private static int[] moveX = {2, 1, -1, -2, -2, -1, 1, 2};
private static int[] moveY = {1, 2, 2, 1, -1, -2, -2, -1};

public static boolean knightsTour(int n) {

int[][] board = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = -1;
}
}

if (backtrack(0, 0, 0, board, n)) {

printBoard(board, n);
return true;
}
return false;
}

private static boolean isSafe(int x, int y, int[][] board, int n) {

return x >= 0 && x < n && y >= 0 && y < n && board[x][y] == -1;
}

private static boolean backtrack(int x, int y, int moveCount, int[][]

board, int n) {
board[x][y] = moveCount;

if (moveCount == n * n - 1) return true;

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

int nextX = x + moveX[i];
int nextY = y + moveY[i];

if (isSafe(nextX, nextY, board, n)) {

if (backtrack(nextX, nextY, moveCount + 1, board, n))
return true;
}
}

board[x][y] = -1;
return false;
}

private static void printBoard(int[][] board, int n) {

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.printf("%2d ", board[i][j]);
}
System.out.println();
}
}
}

C++ Solution

BY: coding_error1
#include <vector>
#include <iostream>
#include <iomanip>
using namespace std;

class KnightsTour {
private:
int moveX[8] = {2, 1, -1, -2, -2, -1, 1, 2};
int moveY[8] = {1, 2, 2, 1, -1, -2, -2, -1};

public:
bool knightsTour(int n) {
vector<vector<int>> board(n, vector<int>(n, -1));

if (backtrack(0, 0, 0, board, n)) {

printBoard(board, n);
return true;
}
return false;
}

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

bool backtrack(int x, int y, int moveCount, vector<vector<int>>& board,

int n) {
board[x][y] = moveCount;

if (moveCount == n * n - 1) return true;

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

int nextX = x + moveX[i];
int nextY = y + moveY[i];

if (isSafe(nextX, nextY, board, n)) {

if (backtrack(nextX, nextY, moveCount + 1, board, n))
return true;
}
}

board[x][y] = -1;
return false;
}

void printBoard(vector<vector<int>>& board, int n) {

for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << setw(3) << board[i][j] << " ";
}
cout << endl;
}
}
};

12. Hamilton Path

Problem: Find a path in a graph that visits each vertex exactly once.

BY: coding_error1
Python Solution
def hamilton_path(graph):
n = len(graph)
path = []
visited = [False] * n

def backtrack(vertex):
path.append(vertex)
visited[vertex] = True

if len(path) == n:
return True

for next_vertex in range(n):

if graph[vertex][next_vertex] == 1 and not
visited[next_vertex]:
if backtrack(next_vertex):
return True

path.pop()
visited[vertex] = False
return False

# Try starting from each vertex

for start in range(n):
if backtrack(start):
return path
path.clear()
visited = [False] * n

return None

# Example usage
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]
]
result = hamilton_path(graph)
print(result)

Java Solution
import java.util.*;

public class HamiltonPath {

public static List<Integer> hamiltonPath(int[][] graph) {
int n = graph.length;
List<Integer> path = new ArrayList<>();
boolean[] visited = new boolean[n];

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

if (backtrack(graph, start, path, visited, n)) {
return new ArrayList<>(path);
}
path.clear();
Arrays.fill(visited, false);

BY: coding_error1
 }
return null;
}

private static boolean backtrack(int[][] graph, int vertex,

List<Integer> path,
boolean[] visited, int n) {
path.add(vertex);
visited[vertex] = true;

if (path.size() == n) return true;

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

if (graph[vertex][nextVertex] == 1 && !visited[nextVertex]) {
if (backtrack(graph, nextVertex, path, visited, n)) return
true;
}
}

path.remove(path.size() - 1);
visited[vertex] = false;
return false;
}
}

C++ Solution
#include <vector>
using namespace std;

class HamiltonPath {
public:
vector<int> hamiltonPath(vector<vector<int>>& graph) {
int n = graph.size();
vector<int> path;
vector<bool> visited(n, false);

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

if (backtrack(graph, start, path, visited, n)) {
return path;
}
path.clear();
fill(visited.begin(), visited.end(), false);
}
return {};
}

private:
bool backtrack(vector<vector<int>>& graph, int vertex, vector<int>&
path,
vector<bool>& visited, int n) {
path.push_back(vertex);
visited[vertex] = true;

if (path.size() == n) return true;

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

if (graph[vertex][nextVertex] == 1 && !visited[nextVertex]) {
if (backtrack(graph, nextVertex, path, visited, n)) return
true;

BY: coding_error1
 }
}

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

13. Expression Add Operators

Problem: Add operators (+, -, *) to make expression equal to target.

Python Solution
def add_operators(num, target):
result = []

def backtrack(index, expression, value, prev_operand):

if index == len(num):
if value == target:
result.append(expression)
return

for i in range(index, len(num)):

current_str = num[index:i + 1]
current_num = int(current_str)

# Skip numbers with leading zeros (except single zero)

if len(current_str) > 1 and current_str[0] == '0':
break

if index == 0:
backtrack(i + 1, current_str, current_num, current_num)
else:
# Addition
backtrack(i + 1, expression + '+' + current_str,
value + current_num, current_num)

# Subtraction
backtrack(i + 1, expression + '-' + current_str,
value - current_num, -current_num)

# Multiplication
backtrack(i + 1, expression + '*' + current_str,
value - prev_operand + prev_operand * current_num,
prev_operand * current_num)

backtrack(0, "", 0, 0)
return result

# Example usage
print(add_operators("123", 6)) # ["1+2+3", "1*2*3"]

Java Solution
import java.util.*;

BY: coding_error1
public class ExpressionAddOperators {
public static List<String> addOperators(String num, int target) {
List<String> result = new ArrayList<>();
backtrack(num, target, 0, "", 0, 0, result);
return result;
}

private static void backtrack(String num, int target, int index, String
expression,
long value, long prevOperand, List<String>
result) {
if (index == num.length()) {
if (value == target) {
result.add(expression);
}
return;
}

for (int i = index; i < num.length(); i++) {

String currentStr = num.substring(index, i + 1);
long currentNum = Long.parseLong(currentStr);

if (currentStr.length() > 1 && currentStr.charAt(0) == '0')

break;

if (index == 0) {
backtrack(num, target, i + 1, currentStr, currentNum,
currentNum, result);
} else {
backtrack(num, target, i + 1, expression + "+" +
currentStr,
value + currentNum, currentNum, result);

backtrack(num, target, i + 1, expression + "-" +

currentStr,
value - currentNum, -currentNum, result);

backtrack(num, target, i + 1, expression + "*" +

currentStr,
value - prevOperand + prevOperand * currentNum,
prevOperand * currentNum, result);
}
}
}
}

C++ Solution
#include <vector>
#include <string>
using namespace std;

class ExpressionAddOperators {
public:
vector<string> addOperators(string num, int target) {
vector<string> result;
backtrack(num, target, 0, "", 0, 0, result);
return result;
}

BY: coding_error1
private:
void backtrack(string& num, int target, int index, string expression,
long long value, long long prevOperand, vector<string>&
result) {
if (index == num.length()) {
if (value == target) {
result.push_back(expression);
}
return;
}

for (int i = index; i < num.length(); i++) {

string currentStr = num.substr(index, i - index + 1);
long long currentNum = stoll(currentStr);

if (currentStr.length() > 1 && currentStr[0] == '0') break;

if (index == 0) {
backtrack(num, target, i + 1, currentStr, currentNum,
currentNum, result);
} else {
backtrack(num, target, i + 1, expression + "+" +
currentStr,
value + currentNum, currentNum, result);

backtrack(num, target, i + 1, expression + "-" +

currentStr,
value - currentNum, -currentNum, result);

backtrack(num, target, i + 1, expression + "*" +

currentStr,
value - prevOperand + prevOperand * currentNum,
prevOperand * currentNum, result);
}
}
}
};

14. Restore IP Addresses

Problem: Restore all valid IP addresses from a string containing only digits.

Python Solution
def restore_ip_addresses(s):
result = []

def is_valid(segment):
if not segment or len(segment) > 3:
return False
if len(segment) > 1 and segment[0] == '0':
return False
return 0 <= int(segment) <= 255

def backtrack(index, segments):

if len(segments) == 4:
if index == len(s):
result.append('.'.join(segments))
return

BY: coding_error1
 if len(segments) >= 4 or index >= len(s):
return

for i in range(index, min(index + 3, len(s))):

segment = s[index:i + 1]
if is_valid(segment):
segments.append(segment)
backtrack(i + 1, segments)
segments.pop()

backtrack(0, [])
return result

# Example usage
print(restore_ip_addresses("25525511135"))

Java Solution
import java.util.*;

public class RestoreIPAddresses {

public static List<String> restoreIpAddresses(String s) {
List<String> result = new ArrayList<>();
backtrack(s, 0, new ArrayList<>(), result);
return result;
}

private static void backtrack(String s, int index, List<String>

segments,
List<String> result) {
if (segments.size() == 4) {
if (index == s.length()) {
result.add(String.join(".", segments));
}
return;
}

if (segments.size() >= 4 || index >= s.length()) return;

for (int i = index; i < Math.min(index + 3, s.length()); i++) {

String segment = s.substring(index, i + 1);
if (isValid(segment)) {
segments.add(segment);
backtrack(s, i + 1, segments, result);
segments.remove(segments.size() - 1);
}
}
}

private static boolean isValid(String segment) {

if (segment.isEmpty() || segment.length() > 3) return false;
if (segment.length() > 1 && segment.charAt(0) == '0') return false;
int num = Integer.parseInt(segment);
return num >= 0 && num <= 255;
}
}

C++ Solution

BY: coding_error1
#include <vector>
#include <string>
using namespace std;

class RestoreIPAddresses {
public:
vector<string> restoreIpAddresses(string s) {
vector<string> result;
vector<string> segments;
backtrack(s, 0, segments, result);
return result;
}

private:
void backtrack(string& s, int index, vector<string>& segments,
vector<string>& result) {
if (segments.size() == 4) {
if (index == s.length()) {
result.push_back(join(segments));
}
return;
}

if (segments.size() >= 4 || index >= s.length()) return;

for (int i = index; i < min(index + 3, (int)s.length()); i++) {

string segment = s.substr(index, i - index + 1);
if (isValid(segment)) {
segments.push_back(segment);
backtrack(s, i + 1, segments, result);
segments.pop_back();
}
}
}

bool isValid(string& segment) {

if (segment.empty() || segment.length() > 3) return false;
if (segment.length() > 1 && segment[0] == '0') return false;
int num = stoi(segment);
return num >= 0 && num <= 255;
}

string join(vector<string>& segments) {

string result = segments[0];
for (int i = 1; i < segments.size(); i++) {
result += "." + segments[i];
}
return result;
}
};

15. Word Break II

Problem: Break a string into words from a dictionary and return all possible sentences.

Python Solution
def word_break(s, word_dict):
word_set = set(word_dict)

BY: coding_error1
 result = []

def backtrack(index, current_sentence):

if index == len(s):
result.append(' '.join(current_sentence))
return

for end in range(index + 1, len(s) + 1):

word = s[index:end]
if word in word_set:
current_sentence.append(word)
backtrack(end, current_sentence)
current_sentence.pop()

backtrack(0, [])
return result

# Example usage
s = "catsanddog"
word_dict = ["cat", "cats", "and", "sand", "dog"]
print(word_break(s, word_dict))

Java Solution
import java.util.*;

public class WordBreakII {

public static List<String> wordBreak(String s, List<String> wordDict) {
Set<String> wordSet = new HashSet<>(wordDict);
List<String> result = new ArrayList<>();
backtrack(s, 0, new ArrayList<>(), wordSet, result);
return result;
}

private static void backtrack(String s, int index, List<String>

currentSentence,
Set<String> wordSet, List<String> result) {
if (index == s.length()) {
result.add(String.join(" ", currentSentence));
return;
}

for (int end = index + 1; end <= s.length(); end++) {

String word = s.substring(index, end);
if (wordSet.contains(word)) {
currentSentence.add(word);
backtrack(s, end, currentSentence, wordSet, result);
currentSentence.remove(currentSentence.size() - 1);
}
}
}
}

C++ Solution
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;

BY: coding_error1
class WordBreakII {
public:
vector<string> wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
vector<string> result;
vector<string> currentSentence;
backtrack(s, 0, currentSentence, wordSet, result);
return result;
}

private:
void backtrack(string& s, int index, vector<string>& currentSentence,
unordered_set<string>& wordSet, vector<string>& result)
{
if (index == s.length()) {
result.push_back(join(currentSentence));
return;
}

for (int end = index + 1; end <= s.length(); end++) {

string word = s.substr(index, end - index);
if (wordSet.count(word)) {
currentSentence.push_back(word);
backtrack(s, end, currentSentence, wordSet, result);
currentSentence.pop_back();
}
}
}

string join(vector<string>& words) {

if (words.empty()) return "";
string result = words[0];
for (int i = 1; i < words.size(); i++) {
result += " " + words[i];
}
return result;
}
};

BY: coding_error1