# Posts published in “Backtracking”

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example 1:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
Output: true

Example 3:

Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
Output: false

Constraints:

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board and word consists of only lowercase and uppercase English letters.

Idea:

DFS

Solution:

/**
* @param {character[][]} board
* @param {string} word
* @return {boolean}
*/
var exist = function(board, word) {
for (let x = 0; x < board[0].length; x++)
for (let y = 0; y < board.length; y++)
if (dfs(board, word, 0, x, y)) return true;
return false;
};

function dfs(board, word, i, x, y) {
// exit recursion:
if (x < 0 || y < 0 || x >= board[0].length || y >= board.length || word[i] !== board[y][x])
return false;
// found the last letter
if (i === word.length - 1)
return true;

let cur = board[y][x];
// mark it 0 means already visit
board[y][x] = 0;
let found = dfs(board, word, i + 1, x + 1, y) ||
dfs(board, word, i + 1, x - 1, y) ||
dfs(board, word, i + 1, x, y + 1) ||
dfs(board, word, i + 1, x, y - 1);
// recover
board[y][x] = cur;
return found;
}

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Example 2:

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 100
• -104 <= matrix[i][j], target <= 104

Solution 1: (DFS)

/**
* @param {number[][]} matrix
* @param {number} target
* @return {boolean}
*/
var searchMatrix = function(matrix, target) {
return dfs(matrix, target, 0, 0);
};

function dfs(matrix, target, x, y) {
let rows = matrix.length;
let cols = matrix[0].length;

// exit recursion condition, reach to the end;
if (y === rows) return false;

// traverse from left to right, then next row
let nextX = (x + 1) % cols;
let nextY = nextX === 0 ? y + 1 : y;

if (matrix[y][x] === target)
return true;
else
return dfs(matrix, target, nextX, nextY);

return false;
}

Solution 2: (Binary Search) Better and Faster!

• Time complexity: O(log(mn))
• Space complexity: O(1)
var searchMatrix = function(matrix, target) {
let cols = matrix[0].length;
// 	treat 2D as 1D, use binary search
let l = 0;
let r = matrix.length * cols;
while (l < r) {
let mid = l + Math.floor((r - l) / 2);
let row = Math.floor(mid / cols);
let col = mid % cols;
if (matrix[row][col] === target) {
return true;
} else if (matrix[row][col] > target) {
r = mid;
} else {
l = mid + 1;
}
}
return false;
};

Write a program to solve a Sudoku puzzle by filling the empty cells.

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.

The '.' character indicates empty cells.

Example 1:

Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
Explanation: The input board is shown above and the only valid solution is shown below:

Constraints:

• board.length == 9
• board[i].length == 9
• board[i][j] is a digit or '.'.
• It is guaranteed that the input board has only one solution.

Idea:

Create 3 tracking arrays:
1 - 9 occur once in whole row, whole col, whole box.
[ith row][number] [ith col][number] [ith box][number]
ex: [ith row][N] = 1 means ith row already use number N
DFS/Backtracking
Travese the board from left to right, row by row
Try to fill 1-9, success return,
if not success, recover data and try next element

Solution:

/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var solveSudoku = function(board) {
// 1 - 9 occur once in whole row, whole col, whole box
// [ith row][number] [ith col][number] [ith box][number]
// ex: [ith row][N] = 1 means ith row already use number N
let rows = Array.from(new Array(9), () => new Array(10).fill(0));
let cols = Array.from(new Array(9), () => new Array(10).fill(0));
let boxes = Array.from(new Array(9), () => new Array(10).fill(0));

for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
const c = board[i][j];
if (c !== '.') {
let num = parseInt(c);
let bx = Math.floor(j / 3);
let by = Math.floor(i / 3);
rows[i][num] = 1;
cols[j][num] = 1;
boxes[by * 3 + bx][num] = 1;
}
}
}
dfs(board, 0, 0, rows, cols, boxes);
};

function dfs(board, x, y, rows, cols, boxes) {
// exit recursion condition, reach to the end;
if (y === 9) return true;

// traverse from left to right, then next row
let nextX = (x + 1) % 9;
let nextY = nextX === 0 ? y + 1 : y;

// already has number, DFS next element
if (board[y][x] !== '.') return dfs(board, nextX, nextY, rows, cols, boxes);

// fill number from 1 - 9
for (let i = 1; i <= 9; i++) {
let bx = Math.floor(x / 3);
let by = Math.floor(y / 3);
let box_index = by * 3 + bx;
// if not breaking the following 3 rules
if (!rows[y][i] && !cols[x][i] && !boxes[box_index][i]) {
// modify, fill the number
rows[y][i] = 1;
cols[x][i] = 1;
boxes[box_index][i] = 1;
board[y][x] = i.toString();
// Try to fill next element, if success return true, or recover
if (dfs(board, nextX, nextY, rows, cols, boxes)) return true;
// recover data
board[y][x] = '.';
boxes[box_index][i] = 0;
cols[x][i] = 0;
rows[y][i] = 0;
}
}
return false;
}

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

Constraints:

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.

Idea:

Use DFS template

Solution:

/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function(nums) {
let res = [];
let cur = [];
let len = nums.length;
let used = new Array(len).fill(false);
dfs(nums, len, res, cur, used);
return res;
}

function dfs(nums, len, res, cur, used) {
// exit recursive condition
if (cur.length === len) {
res.push(cur.concat());
return;
}

// possible solution
for (let i = 0; i < len; i++) {
// skip used integer
if (used[i]) continue;

// modify current state
used[i] = true;
cur.push(nums[i]);
dfs(nums, len, res, cur, used);
// recover current state
cur.pop();
used[i] = false;
}
}

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output:
[
[1,2,2],
[5]
]

Constraints:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

Idea:

DFS

• Important Step: sort the array
• Create a DFS recursive and keep tracking target value and start index
• Exit DFS recursive:
• if (target < 0) return;
• if (target === 0) record answer and return;
• For loop (Possible solution) pay attention to:
• No duplication
• Candidates can only be used once

Solution:

/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/

var combinationSum2 = function(candidates, target) {
let res = [];
let cur = [];
// Important Step: sort the array
candidates.sort();
dfs(res, cur, 0, candidates, target);
return res;
}

function dfs(res, cur, start, can, target) {
// exit recursive condition
if (target < 0) return;
if (target === 0) {
res.push(cur.concat());
return;
}

for (let i = start; i < can.length; i++) {
// skip duplicate
if (i > start && can[i] === can[i - 1]) continue;
cur.push(can[i]);
// Each number in candidates may only be used once
// in the combination. start from i + 1
dfs(res, cur, i + 1, can, target - can[i]);
cur.pop();
}

}

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Constraints:

• 1 <= n <= 8

Idea:

Backtracking

Solution:

/**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function(n) {
let ans = [];
backtrack(ans, "", 0, 0, n);
return ans;
}

function backtrack(ans, cur, open, close, max){
// exit recursive condition
if (cur.length === max * 2) {
ans.push(cur.concat());
return;
}
// possible solution
if (open < max)
backtrack(ans, cur + "(", open + 1, close, max);
if (close < open)
backtrack(ans, cur + ")", open, close + 1, max);
}

Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*' where:

• '.' Matches any single character.​​​​
• '*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:

Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Example 4:

Input: s = "aab", p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".

Example 5:

Input: s = "mississippi", p = "mis*is*p*."
Output: false

Constraints:

• 0 <= s.length <= 20
• 0 <= p.length <= 30
• s contains only lowercase English letters.
• p contains only lowercase English letters, '.', and '*'.
• It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.

Idea:

Backtracking / Depth-first search (DFS)

There are two normal cases without consideration of *:

1. s === p
2. s !== p, but p === '.' and s is any character

And then let’s consider how to handle the pattern *:

If we have a x* in the pattern(x stands for any character), we may ignore this part of
the pattern, or delete a matching character in the text

// no match: aa , c*                || match: aaa , a*
(isMatch(s, p.substring(2)) || (first_match && isMatch(s.substring(1), p)));

According to these analyses, we can construct a depth-first search algorithm, it’s a recursive algorithm.

Solution:

/**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function(s, p) {
let sLen = s.length;
let pLen = p.length;
if (pLen === 0) return sLen === 0;
let first_match = (sLen !== 0 && (p[0] === s[0] || p[0] === '.'));

// If a star is present in the pattern, it will be in the
// second position p[1]. Then, we may ignore this part of
// the pattern, or delete a matching character in the text.
// If we have a match on the remaining strings after any of
// these operations, then the initial inputs matched.
if (pLen >= 2 && p[1] === '*') {
// no match:  aa , c*       ||      match:       aaa , a*
return (isMatch(s, p.substring(2)) || (first_match && isMatch(s.substring(1), p)));
} else {
return first_match && isMatch(s.substring(1), p.substring(1));
}
};