Backtracking is a brute force algorithm. Suitable for combination, cutting, subset, arrangement, checkerboard (N queen)
Question 1:
Given two integers n and k, return 1… All possible combinations of k numbers in n.
Input: n = 4, k = 2
Output: [[2, 4], [3, 4], [2, 3], [1, 2], [1, 3], [1, 4]]
var combine = function(n, k) { var temp=[]; var res=[]; function dfs(n,k,index){ if(temp.length>=k){ res.push([...temp]); return } for(var i=index; i<=n; i++){ temp.push(i); dfs(n,k,i+1); temp.pop(); }} DFS (n,k,1); return res; };Copy the codeQuestion 2
Given an M x N two-dimensional character grid board and a string word. Return true if Word exists in the grid; Otherwise, return false.
Words must be formed in alphabetical order by letters in adjacent cells, where “adjacent” cells are those that are horizontally or vertically adjacent. Letters in the same cell are not allowed to be reused.
Example 1:
Input: board = [[” A “, “B”, “C”, “E”], [” S “, “F”, “C”, “S”], [” A “, “D”, “E”, “E”]], the word = “ABCCED”
Output: true,
Example 2:
Board = [[“a”,”b”],[“c”,”d”]], word = “abcd”
Output: false
var exist = function(board, word) { const r = board.length; const c = board[0].length; const wordIndexInit=0; for(let i=0; i<r; i++){ for(let j=0; j<c; j++){ if( dfs(board,word,i,j,wordIndexInit)){ return true; } } } return false; function dfs(board,word,i,j,k){ if(i<0||j<0||i>=r||j>=c||board[i][j]! ==word[k]){ return false; } if(k===word.length-1){return true} board[I][j]= res=dfs(board,word,i+1,j,k+1)||dfs(board,word,i-1,j,k+1) ||dfs(board,word,i,j+1,k+1)||dfs(board,word,i,j-1,k+1) If (res = = = true) {return true} else {board [I] [j] = word [k] / / retracement}}};Copy the code