define

Backtracking algorithm is actually a search attempt process similar to enumeration, which is mainly to find the solution of the problem in the search attempt process. When it is found that the solution condition is not met, it will “backtrack” back and try another path. Backtracking is a kind of optimal search method, which searches forward according to the optimal conditions to reach the target. However, when a certain step is explored, it is found that the original choice is not good or fails to reach the target, so it takes a step back to make a new choice. The technology of going back and going again when there is no way is called backtracking method, and the point in a certain state that meets the backtracking condition is called “backtracking point”.

General steps for problem solving with backtracking:

  • For the given problem, the solution space of the problem is defined, which contains at least one (optimal) solution of the problem.
  • The structure of the solution space is determined so that the whole solution space can be easily searched by backtracking.
  • The solution space is searched depth-first, and the pruning function is used to avoid invalid searches.

Backtracking is a modified depth-first search method. The process includes: depth-first search is performed on a state-space tree to check whether each node meets the conditions. If not, go back to the parent of the node. The algorithm framework (pseudocode) is as follows:

Result = [] backtrack(path, select list): if end conditions are met: result.add(path) return for select in Select list: Select backtrack(path, select list) UnselectCopy the code

The core is the recursion in the for loop, making a selection before the recursive call, and then undoing the selection after the recursive call.

Backtracking solution

Here are some typical backtracking questions, which I did myself.

The whole arrangement

Given a sequence without repeating digits, return all possible permutations.

Input: [1, 2, 3] output: [[1, 2, 3], [31] 1,,1,3 [2], [2,3,1], [3,1,2], [3, 2, 1]]Copy the code

Source: leetcode-cn.com/problems/pe…

var permute = function(nums) {
    let len = nums.length;
    let res = [];
    function backTrace(path) {
        if(path.length === len) return res.push(path.slice());
        for (let i = 0; i < len; i++) {
            if(path.indexOf(nums[i]) === -1) {
                path.push(nums[i]);
                backTrace(path);
                path.pop();
            }
        }
    }
    backTrace([]);
    return res;
};
Copy the code

The whole arrangement II

Given a sequence that can contain repeating digits, return all non-repeating permutations.

Input: [1,2] output: [[1,1,2], [1,2,1]]Copy the code

Source: leetcode-cn.com/problems/pe…

var permuteUnique = function(nums) {
    let len = nums.length, res = [], idx = [];
    nums.sort((a, b) => a - b);
    function backTrace(path, idx) {
        if(path.length === len) return res.push(path.slice());
        for (let i = 0; i < len; i++) {
            if((nums[i] === nums[i - 1] && idx.includes(i - 1)) || idx.includes(i)) continue;
            path.push(nums[i]);
            idx.push(i);
            backTrace(path, idx);
            path.pop();
            idx.pop();
        }
    }
    backTrace([], idx);
    return res;
};
Copy the code

A subset of

Given an array of integers with no repeating elements, nums returns all possible subsets (power sets) of the array. ** Description: ** solution set cannot contain duplicate subsets.

Output: input: nums = [1, 2, 3], [[3], [1], [2], [1, 2, 3], [1, 3], [2, 3], [1, 2], []]Copy the code

Source: leetcode-cn.com/problems/su…

var subsets = function(nums) {
    let path = [], res = [];
    let backTrace = (start, nums, path, res) => {
        if(path.length > nums.length) return;
        res.push(path.slice());
        for (let i = start; i < nums.length; i++) {
            path.push(nums[i]);
            backTrace(i + 1, nums, path, res);
            path.pop()
        }
    }
    backTrace(0, nums, path, res);
    return res;
};
Copy the code

Subset II

Given an integer array nums that may contain repeating elements, return all possible subsets (power sets) of that array. ** Description: ** solution set cannot contain duplicate subsets.

,2,2 input: [1] output: [[2], [1],,2,2 [1], [2], [1, 2], []]Copy the code

Source: leetcode-cn.com/problems/su…

var subsetsWithDup = function(nums) {
    let path = [], res = [];
    nums.sort((a, b) => a - b);
    let backTrace = (start, nums, path, res) => {
        if(path.length > nums.length) return;
        res.push(path.slice());
        for (let i = start; i < nums.length; i++) {
            if(start < i && nums[i - 1] === nums[i]) continue;
            path.push(nums[i]);
            backTrace(i + 1, nums, path, res);
            path.pop();
        }
    }
    backTrace(0, nums, path, res);
    return res;
};
Copy the code

combination

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],]Copy the code

Source: leetcode-cn.com/problems/co…

var combine = function(n, k) {
    let res = [], path = [];
    if(k === 0) return [[]];
    function backTrace(start, n, k, path, res) {
        if(path.length === k) return res.push(path.slice());
        for (let i = start; i <= n; i++) {
            path.push(i);
            backTrace(i + 1, n, k, path, res);
            path.pop();
        }
    }
    backTrace(1, n, k, path, res);
    return res;
};
Copy the code

Combined total

Given an array of no duplicate elements and a target number, find all combinations of the candidates that make the numeric sum target. The numbers in the candidates can be selected repeatedly without limit.

Enter: candidates = [2,3,6,7], target = 7Copy the code

Source: leetcode-cn.com/problems/co…

var combinationSum = function(candidates, target) {
    let res = [], path = [], len = candidates.length;
    candidates.sort((a, b) => a - b);
    function backTrace(path, target, start) {
        if(target === 0) return res.push(path.slice());
        for (let i = start; i < len; i++) {
            if(target < candidates[i]) break;
            path.push(candidates[i]);
            backTrace(path, target - candidates[i], i);
            path.pop(candidates[i]);
        }
    }
    backTrace(path, target, 0);
    return res;
};
Copy the code

Sum of combinations II

Given an array of candidates and a target number target, find all combinations of the candidates that can be the sum of the number and target. Each number in the candidates must be used only once in each combination.

Input: candidates =,1,2,7,6,1,5 [10], target = 8, solving sets: [[1, 7], [1, 2, 5], [2, 6], [1, 1, 6]]Copy the code

Source: leetcode-cn.com/problems/co…

var combinationSum2 = function(candidates, target) {
    let res = [], path = [], len = candidates.length;
    candidates.sort((a, b) => a - b);
    function backTrace(path, target, start) {
        if(target === 0) return res.push(path.slice());
        for (let i = start; i < len; i++) {
            if(candidates[i] > target) continue;
            if(i > start && candidates[i - 1] === candidates[i]) continue;
            path.push(candidates[i]);
            backTrace(path, target - candidates[i], i + 1);
            path.pop();
        }
    }
    backTrace(path, target, 0);
    return res;
};
Copy the code

Sum of Combinations III

Find all the combinations of k numbers that add up to n. Only positive integers from 1 to 9 are allowed in a combination, and there are no duplicate digits in each combination.

Input: k = 3, n = 9 output: [[1,2,6], [1,3,5], [2,3,4]]Copy the code

Source: leetcode-cn.com/problems/co…

var combinationSum3 = function(k, n) {
    let path = [], res = [];
    function backTrace(start, k, n, res, path) {
        if(path.length === k && n === 0) return res.push(path.slice());
        for (let i = start; i < 10; i++) {
            path.push(i);
            backTrace(i + 1, k, n - i, res, path);
            path.pop();
        }
    }
    backTrace(1, k, n, res, path);
    return res;
};
Copy the code

String arrangement

Enter a string (with repeated string permutations) and print out all permutations of characters in that string. You can return this array of strings in any order, but no repeating elements.

Input: s = "ABC" output: [" ABC ", "acb", "America", "bca", "cab", "cba"]Copy the code

Source: leetcode-cn.com/problems/zi…

var permutation = function(s) {
    let ans = [];
    function dfs(cur, str) {
        if(str === '') return ans.push(cur);
        for (let i = 0, len = str.length; i < len; i++) {
            if(i > 0 && str[i - 1] === str[i]) continue;
            cur += str[i];
            dfs(cur, str.slice(0, i).concat(str.slice(i + 1)))
            cur = cur.slice(0, cur.length - 1)
        }
    }
    dfs('', s.split('').sort().join(''));
    return ans;
};
Copy the code

Permutations and combinations of non-repeating strings

Permutations and combinations of non-repeating strings. Write a method that evaluates all permutations of a string in which each character is different.

Input: S = "qwe" output: [" qwe ", "qew", "wqe", "weq," "ewq", "eqw"]Copy the code

Source: leetcode-cn.com/problems/pe…

var permutation = function(S) {
    let cur = '', ans = [];
    let backtrace = (cur, str) => {
        if(str === '') {
            ans.push(cur);
        }
        for (let i = 0, len = str.length; i<len; i++) {
            cur += str[i];
            backtrace(cur, str.slice(0, i).concat(str.slice(i+1)));
            cur = cur.slice(0, cur.length - 1);
        }
    }
    backtrace(cur, S);
    return ans;
};
Copy the code

Suitable number

We define the order as an integer in which the digit in each digit is 1 greater than the digit in the preceding digit. Return an ordered list of all sequential degrees in the range [low, high] (in descending order).

Output: low = 1000, high = 13000 output: [45] 1234234 5345 6456 7567 8678 9123Copy the code

Source: leetcode-cn.com/problems/se…

var sequentialDigits = function(low, high) {
    let ans = [];
    for (i = 1; i <= 9; i++) {
        backtrack(low, high, i, i);
    }
    ans.sort((a, b) => a-b)
    return ans;
    function backtrack (low, high, curNum, curTail) {
        if(curNum >= low && curNum <= high) {
            ans.push(curNum);
        }
        if(curNum > high) {
            return;
        }
        if(curTail + 1 <= 9) {
            backtrack(low, high, curNum*10 + curTail + 1, curTail + 1)
        }
    }
};
Copy the code

Recover IP address

Given a string containing only numbers, undo it and return all possible IP address formats. A valid IP address consists of four integers (each integer is between 0 and 255, and cannot contain a leading 0), separated by a hyphen (.).

Input: s = "25525511135" Output: ["255.255.11.135","255.255.111.35"]Copy the code

Source: leetcode-cn.com/problems/re…

var restoreIpAddresses = function(s, res = [], arr = [], start = 0) { if(s.length > 12 || s.length < 4) return res; if(arr.length === 4 && start === s.length) res.push(arr.join('.')); for (let i = start; i < s.length; i++) { let str = s.substring(start, i + 1), strNum = str - 0; if(strNum > 255 || str ! = strNum + '') break; arr.push(str); restoreIpAddresses(s, res, arr, i+1); arr.pop(); } return res; };Copy the code

Split palindrome string

Given a string s, divide s into substrings such that each substring is a palindrome string. Returns all possible segmentation schemes for S.

Input: "aab" Output: [[" AA ","b"], [" A ","a","b"]Copy the code

Source: leetcode-cn.com/problems/pa…

var partition = function(s) { let ans = [], path = []; let backTrace = (start, path) => { if(start === s.length) return ans.push(path.slice()); for (let i = start; i < s.length; i++) { if(! isPalindrome(start, i)) continue; path.push(s.slice(start, i + 1)); backTrace(i + 1, path); path.pop(); } } function isPalindrome(start, end) { let l = start, h = end; while(l < h) { if(s[l++] ! == s[h--]) return false; } return true; } backTrace(0, path); return ans; };Copy the code

All letters are uppercase and lowercase

Given a string S, we get a new string by caseshifting each letter in string S. Returns a collection of all possible strings.

Input: S = "a1b2" output: [" a1b2 ", "a1b2", "a1b2", "a1b2"] input: S = "3 z4" output: [" 3 z4 ", "3 z4"] input: S = "12345" output: [" 12345 "]Copy the code

Source: leetcode-cn.com/problems/le…

var letterCasePermutation = function(S) {
    const res = [];
    const backTrace = (start, str) => {
        res.push(str);
        for (let i = start; i < str.length; i++) {
            if(str[i] >= 'a' && str[i] <= 'z') {
                backTrace(i+1, str.slice(0, i) + str[i].toUpperCase() + str.slice(i+1));
            } else if(str[i] >= 'A' && str[i] <= 'Z') {
                backTrace(i+1, str.slice(0, i) + str[i].toLowerCase() + str.slice(i+1));
            }
        }
    }
    backTrace(0, S);
    return res;
};
Copy the code

Parentheses generates

The number n represents the logarithm of parentheses generated. Design a function that generates all possible and valid parentheses combinations.

Input: n = 3 output: [" ((())) ", "() () ()", "() () ()", "() () ()", "() () ()"]Copy the code

Source: leetcode-cn.com/problems/ge…

var generateParenthesis = function(n) { if(! n) return []; let res = []; let dfs = (subs, left, right, n) => { if(left === n && right === n) { res.push(subs); return; } if(left < right) { return; } left < n && dfs(subs + '(', left + 1, right, n); right < n && dfs(subs + ')', left, right + 1, n); } dfs('', 0, 0, n); return res; };Copy the code

N queen

Design an algorithm to print various positions of N queens on an N × N checkerboard, where each queen is not in a row, column, or diagonal. By “diagonals” I mean all diagonals, not just the two that divide the entire board.

Input: 4 output: [[. "q..", "... Q ", "Q...", ".. Q. "], [".. Q. ", "Q...", "... Q ", ". Q.. "]] : 4 queen problem have the following two different solutions. [[" Q.. ", / / solution 1... "Q", "Q...", ".. Q. "], [".. Q., / / solution 2 "Q...", "... Q ", ". Q.. "]]Copy the code

Source: leetcode-cn.com/problems/ei…

Var solveNQueens = function(n) {let queens = new Array(n); let res = []; // let cols = new Array(n); Let leftTop = new Array((n << 1) -1); // Let rightTop = new Array(leftTop.length); place(0); return res; function place(row) { if(row === cols.length) { let arr = []; for (let i in queens) { arr.push('Q'.padStart(queens[i] + 1, '.').padEnd(n, '.')) } res.push(arr) return res; } for (let col = 0; col < cols.length; col++) { if(cols[col]) continue; Let ltIndex = row-col + cols.length-1; if(leftTop[ltIndex]) continue; Let rtIndex = row + col; if(rightTop[rtIndex]) continue; queens[row] = col; cols[col] = true; leftTop[ltIndex] = true; rightTop[rtIndex] = true; place(row + 1); cols[col] = false; leftTop[ltIndex] = false; rightTop[rtIndex] = false; }}}; var solveNQueens = function(n) { if(n < 1) return; let res = []; Let cols = new Array(n); place(0); return res; function place(row) { if(row === n) { show(); return; } for (let col = 0; col < n; col++) { if(isValid(row, col)) { cols[row] = col; place(row + 1); } } } function isValid(row, col) { for (let i = 0; i < row; i++) { if(cols[i] === col) { return false; } if(row - i === Math.abs(col - cols[i])) { return false; } } return true; } function show() { let arr = []; for (let row = 0; row < n; row++) { for (let col = 0; col < n; col++) { if(cols[row] === col) { arr.push('Q'.padStart(cols[row] + 1, '.').padEnd(n, '.')) } } } res.push(arr); }};Copy the code

N queen II

The n Queens problem is the study of how to place n queens on an n by n board so that queens cannot attack each other. Given an integer n, return the number of different solutions for n queens.

Input: 4 Output: 2 Explanation: 4 Queen problem has the following two different solutions. [[" Q.. ", / / solution 1... "Q", "Q...", ".. Q. "], [".. Q., / / solution 2 "Q...", "... Q ", ". Q.. "]]Copy the code

Source: leetcode-cn.com/problems/n-…

var totalNQueens = function(n) { let counts = 0; let cols = new Array(n); let leftTop = new Array((n << 1) - 1); let rightTop = new Array(leftTop.length); place(0); return counts; function place(row) { if(row === cols.length) { counts++; return; } for (let col = 0; col < cols.length; col++) { if(cols[col]) continue; let ltIndex = row - col + cols.length - 1; if(leftTop[ltIndex]) continue; let rtIndex = row + col; if(rightTop[rtIndex]) continue; cols[col] = true; leftTop[ltIndex] = true; rightTop[rtIndex] = true; place(row + 1); cols[col] = false; leftTop[ltIndex] = false; rightTop[rtIndex] = false; }}}; var totalNQueens = function(n) { if(n < 1) return; let count = 0; Let cols = new Array(n); place(0); return count; function place(row) { if(row === n) { count++; return; } for (let col = 0; col < n; Cols [row] = col; cols[row] = col; cols[row] = col; place(row + 1); } } } function isValid(row, col) { for (let i = 0; i < row; If (cols[I] === col) {return false; if(cols[I] == col) {return false; If (row - I === = math. abs(col-cols [I])) {return false; } } return true; }};Copy the code

A combination of letters for a telephone number

Given a string containing only the numbers 2-9, return all the letter combinations it can represent. The mapping of numbers to letters is given as follows (same as a telephone key). Note that 1 does not correspond to any letter.

Input: "23" output: [" AD ", "ae", "af", "bd", "be", "bf", "CD" and "ce", "cf"].Copy the code

Source: leetcode-cn.com/problems/le…

var letterCombinations = function(digits) { if(! digits) return []; let phone = {2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz'} let ans = [], arr = []; for (let digit of digits) { arr.push(phone[digit]) } let backtrace = (str = '', index = 0) => { if(index === digits.length) { ans.push(str) } else { for (let i of arr[index]) { let tmp = str + i; backtrace(tmp, index + 1) } } } backtrace() return ans; };Copy the code