Recusion and Backtracking
Print All Permutations of a String/Array
❓: Print All Permutations of a String/Array
Example:
Input: arr = [1, 2, 3]
Output: [ [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] ]
🧠:
1. Keep track of seen elements.
2. At every index, try all possible.
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
self.nums = nums
self.n = len(nums)
self.res = []
self.helper()
return self.res
def helper(self, seen=set(), curr=[]):
if len(seen) == self.n:
self.res.append(curr[:])
return
for ind in range(self.n):
if ind not in seen:
seen.add(ind)
curr.append(self.nums[ind])
self.helper()
seen.remove(ind)
curr.pop()
use std::collections::HashSet;
impl Solution {
pub fn permute(nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut res: Vec<Vec<i32>> = Vec::new();
let mut seen: HashSet<usize> = HashSet::new();
let mut curr: Vec<i32> = Vec::new();
Solution::helper(&mut curr, &nums, &mut seen, &mut res);
res
}
fn helper(curr: &mut Vec<i32>, nums: &Vec<i32>, seen: &mut HashSet<usize>, res: &mut Vec<Vec<i32>>){
if seen.len() == nums.len(){
res.push(curr.clone());
}
for i in 0..nums.len(){
if !seen.contains(&i){
seen.insert(i);
curr.push(nums[i]);
Solution::helper(curr, nums, seen, res);
seen.remove(&i);
curr.pop();
}
}
}
}
N Queen Problem
❓: The n-queens is the problem of placing n queens on n × n chessboard such that no two queens can attack each other. Given an integer n, return all distinct solutions to the n -queens puzzle. Each solution contains a distinct boards configuration of the queen's placement, where ‘Q’ and ‘.’ indicate queen and empty space respectively.
Example:
Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
🧠:
1. At every position, check whether it is a valid position or not.
2. If yes, repeat process until we reach end index.
3. If no, backtrack and repeat the process
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
self.res = []
self.n = n
board = [["."] * n for _ in range(n)]
self.helper(board)
return self.res
def helper(self, board, ind=0):
if ind == self.n:
self.res.append(["".join(item) for item in board])
return
for i in range(self.n):
if self.is_valid(ind, i, board):
board[ind][i] = "Q"
self.helper(board, ind + 1)
board[ind][i] = "."
def is_valid(self, row, col, board) -> bool:
# up
r = row - 1
while r >= 0:
if board[r][col] == "Q":
return False
r -= 1
# left diagonal
r, c = row - 1, col - 1
while r >= 0 and c >= 0:
if board[r][c] == "Q":
return False
r -= 1
c -= 1
# up diagonal
r, c = row - 1, col + 1
while r >= 0 and c < self.n:
if board[r][c] == "Q":
return False
r -= 1
c += 1
return True
impl Solution {
pub fn solve_n_queens(n: i32) -> Vec<Vec<String>> {
let mut res: Vec<Vec<String>> = Vec::new();
let n = n as usize;
let mut board: Vec<Vec<char>> = Vec::new();
for _ in 0..n {
board.push(vec!['.'; n as usize]);
}
Solution::helper(&mut board, 0, n, &mut res);
res
}
fn helper(board: &mut Vec<Vec<char>>, ind: usize, n: usize, res: &mut Vec<Vec<String>>) {
if ind == n {
Solution::add_board(board.clone(), res);
}
for i in 0..n {
if Solution::is_valid(ind, i, board, n) {
board[ind][i] = 'Q';
Solution::helper(board, ind + 1, n, res);
board[ind][i] = '.';
}
}
}
fn add_board(board: Vec<Vec<char>>, res: &mut Vec<Vec<String>>) {
let mut new_board: Vec<String> = Vec::new();
for item in board {
new_board.push(item.iter().collect());
}
res.push(new_board);
}
fn is_valid(row: usize, col: usize, board: &mut Vec<Vec<char>>, n: usize) -> bool {
if row == 0 {
return true;
}
//up
let mut r = row - 1;
while r >= 0 {
if board[r][col] == 'Q' {
return false;
}
if r == 0 {
break;
}
r -= 1
}
//right diagonal
let (mut r, mut c) = (row - 1, col + 1);
while r >= 0 && c < n {
if board[r][c] == 'Q' {
return false;
}
if r == 0 {
break;
}
r -= 1;
c += 1;
}
if col == 0 {
return true;
}
//left diagonal
let (mut r, mut c) = (row - 1, col - 1);
while r >= 0 && c >= 0 {
if board[r][c] == 'Q' {
return false;
}
if r == 0 || c == 0 {
break;
}
r -= 1;
c -= 1;
}
true
}
}
Sudoku Solver
❓: Given a 9x9 incomplete sudoku, solve it such that it becomes valid sudoku.
Example:
class Solution:
def solveSudoku(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
self.b = board
self.helper()
def helper(self):
for i in range(9):
for j in range(9):
if self.b[i][j] == ".":
for digit in "123456789":
if self.is_valid(i, j, digit):
self.b[i][j] = digit
if self.helper():
return True
self.b[i][j] = "."
return False
return True
def is_valid(self, row, col, digit):
for i in range(9):
for j in range(9):
if self.b[i][col] == digit or self.b[row][j] == digit:
return False
grid_row, grid_col = (row // 3) * 3, (col // 3) * 3
for i in range(grid_row, grid_row + 3):
for j in range(grid_col, grid_col + 3):
if self.b[i][j] == digit:
return False
return True
impl Solution {
pub fn solve_sudoku(board: &mut Vec<Vec<char>>) {
Solution::helper(board);
}
fn helper(b: &mut Vec<Vec<char>>) -> bool {
for i in 0..9 {
for j in 0..9 {
if b[i][j] == '.' {
for c in "123456789".chars() {
if Solution::is_valid(i, j, b, c) {
b[i][j] = c;
if Solution::helper(b) == true {
return true;
}
b[i][j] = '.';
}
}
return false;
}
}
}
true
}
fn is_valid(r: usize, c: usize, b: &Vec<Vec<char>>, digit: char) -> bool {
for i in 0..9 {
for j in 0..9 {
if b[r][j] == digit || b[i][c] == digit {
return false;
}
}
}
let (grid_row, grid_col) = ((r / 3) * 3, (c / 3) * 3);
for i in grid_row..grid_row + 3 {
for j in grid_col..grid_col + 3 {
if b[i][j] == digit {
return false;
}
}
}
true
}
}
M Coloring Problem
❓: Given an undirected graph and a number m, determine if the graph can be colored with at most m colors such that no two adjacent vertices of the graph are colored with the same color.
Example:
Input: N = 4 M = 3 E = 5
Edges[] = { (0, 1), (1, 2), (2, 3), (3, 0), (0, 2) }
Output: 1
🧠:
1. Form the graph as adjacency list.
2. For every node, try to color all the colors.
3. If able to color the node with particular color, store it and move to next node.
4. Once all nodes are colored, return True, else return False.
from collections import defaultdict
class Solution:
def graphColoring(self, edges, m, n):
self.adj = defaultdict(list)
for edge in edges:
self.adj[edge[0]].append(edge[1])
self.adj[edge[1]].append(edge[0])
self.m = m
self.n = n
return self.helper()
def helper(self, curr_node=0, colored={}):
if curr_node == self.n:
return True
for color in range(self.m):
if self.is_valid(curr_node, colored, color):
colored[curr_node] = color
if self.helper(curr_node + 1):
return True
return False
def is_valid(self, node, colored, color) -> bool:
for adj_node in self.adj[node]:
if colored.get(adj_node) == color:
return False
return True
Rat in a Maze
❓: Consider a rat placed at (0, 0) in a square matrix of order N * N. It has to reach the destination at (N - 1, N - 1). Find all possible paths that the rat can take to reach from source to destination. The directions in which the rat can move are 'U'(up), 'D'(down), 'L' (left), 'R' (right). Value 0 at a cell in the matrix represents that it is blocked and the rat cannot move to it while value 1 at a cell in the matrix represents that rat can travel through it.
Note: In a path, no cell can be visited more than one time.
Print the answer in lexicographical(sorted) order
Example:
Input:
N = 4
m[][] = {{1, 0, 0, 0},
{1, 1, 0, 1},
{1, 1, 0, 0},
{0, 1, 1, 1}}
Output: DDRDRR DRDDRR
class Solution:
def findPath(self, mat):
self.mat = mat
self.n = len(mat)
self.res = []
self.helper()
return sorted(self.res)
def helper(self, r=0, c=0, curr="", seen=set()):
if not self.is_valid(r, c, seen):
return
if r == self.n - 1 and c == self.n - 1:
self.res.append(curr)
return
seen.add((r, c))
self.helper(r + 1, c, curr + "D")
self.helper(r - 1, c, curr + "U")
self.helper(r, c + 1, curr + "R")
self.helper(r, c - 1, curr + "L")
seen.remove((r, c))
def is_valid(self, r, c, seen):
return not (
r < 0
or c < 0
or r >= self.n
or c >= self.n
or (r, c) in seen
or not self.mat[r][c]
)
Word Break (print all ways)
❓: You are given a non-empty string S containing no spaces’ and a dictionary of non-empty strings (say the list of words). You are supposed to construct and return all possible sentences after adding spaces in the originally given string ‘S’, such that each word in a sentence exists in the given dictionary.
Note : The same word in the dictionary can be used multiple times to make sentences. Assume that the dictionary does not contain duplicate words.
Example:
1
6
god is now no where here
godisnowherenowhere
Output:
god is no where no where
god is no where now here
god is now here no where
god is now here now here
class Solution:
def wordBreak(self, s, dictionary):
self.s = s
self.n = len(s)
self.words = set(dictionary)
self.res = []
self.helper()
return self.res
def helper(self, curr_ind=0, curr=[]):
if curr_ind == self.n:
self.res.append(curr[:])
return
for i in range(curr_ind, self.n):
if self.s[curr_ind : i + 1] in self.words:
curr.append(self.s[curr_ind : i + 1])
self.helper(i + 1)
curr.pop()
use std::collections::HashSet;
impl Solution {
pub fn word_break(s: String, word_dict: Vec<String>) -> Vec<String> {
let mut res: Vec<String> = Vec::new();
let mut word_set: HashSet<String> = word_dict.into_iter().collect();
let mut curr: Vec<String> = Vec::new();
Solution::helper(&s, &word_set, &mut res, 0, &mut curr);
res
}
fn helper(
s: &String,
word_set: &HashSet<String>,
res: &mut Vec<String>,
ind: usize,
curr: &mut Vec<String>,
) {
if ind == s.len() {
res.push(curr.join(" "));
return;
}
for i in ind..s.len() {
let curr_string = &s[ind..i + 1];
if word_set.contains(curr_string) {
curr.push(curr_string.to_string());
Solution::helper(&s, word_set, res, i + 1, curr);
curr.pop();
}
}
}
}