Template — source lanbulandong

result = []
def backtrack(Path, selection list): 
	ifEnd conditions are met: result.add(path) return
      
	forSelect in Select list: Make a selectionbacktrack(Path, selection list)Cancel the choiceCopy the code

Subset problem

1. All subsets of an array with no repeating elements

Leetcode-cn.com/problems/su…

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
        if(n == 0 )return res;
        List<Integer> list = new ArrayList<>();
        dfs(nums , 0 , list);
        return res;
    }

    void dfs(int[] nums , int start , List<Integer> list){
        res.add(new ArrayList<>(list));

        for(int i = start ; i < nums.length ; i++){
            list.add(nums[i]);
            dfs(nums , i+1 , list);
            list.remove(list.size()-1); }}}Copy the code

2. All subsets of an array with repeating elements

Leetcode-cn.com/problems/su…

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        int n = nums.length;
        if(n == 0) return res;
        Arrays.sort(nums);
        List<Integer> list = new ArrayList<>();
        dfs(nums , 0 , list);
        return res;
    }

    void dfs(int[] nums , int start , List<Integer> list){
        res.add(new ArrayList<>(list));
        for(int i = start ; i < nums.length ; i++){
            if(i > start && nums[i] == nums[i-1])continue;
            list.add(nums[i]);
            dfs(nums , i+1 , list);
            list.remove(list.size()-1); }}}Copy the code

Total permutation problem

1. Complete permutation of non-repeating digits

Leetcode-cn.com/problems/pe…

class Solution {
    List<List<Integer>> res =  new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        if(nums.length == 0) return res;
        List<Integer> list  = new ArrayList<>();
        boolean[] isv = new boolean[nums.length]; // Full array, each number can only be used once, using a Boolean array to determine whether it has been accessed
        dfs(nums , list , isv);
        return res;
    }

	// Since each permutation is from the beginning of the array to the end of the array, there is no need to pass start
    void dfs(int[] nums  ,List<Integer> list , boolean[] isv){
        if(list.size() == nums.length){ // The end condition is met
            res.add(new ArrayList<>(list));
            return;
        }

        for(int i = 0 ; i < nums.length ; i++){
            if(isv[i]) continue;  // Continue if already selected
            list.add(nums[i]);	/ / to make a choice
            isv[i] = true;
            dfs(nums , list , isv);
            list.remove(list.size()-1); / / cancel
            isv[i] = false; }}}Copy the code

2. Full permutations with repeated numbers

Leetcode-cn.com/problems/pe…

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<Integer> list = new ArrayList<>();
        int n = nums.length;
        if(n == 0) return res;
        Arrays.sort(nums); // Sort first
        boolean[] isv = new boolean[n];
        dfs(nums , list , isv);
        return res;
    }

    void dfs(int[] nums , List<Integer> list , boolean[] isv){
        if(list.size() == nums.length){
            res.add(new ArrayList<>(list));
            return;
        }

        for(int i = 0 ; i < nums.length ; i++){
            if(i > 0 && nums[i] == nums[i-1] && isv[i-1]) continue; 
            if(isv[i]) continue;
            list.add(nums[i]);
            isv[i] = true;
            dfs(nums , list , isv);
            list.remove(list.size()-1);
            isv[i] = false; }}}Copy the code

3. List all paths in the binary tree

Leetcode-cn.com/problems/bi…

class Solution {
    List<String> res = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        if(root == null) return res;
        StringBuilder sb = new StringBuilder();
        dfs(root , sb);
        return res;
    }

    void dfs(TreeNode root , StringBuilder sb){
        if(root == null) return;

        int n = sb.length();
        sb.append(root.val);
        sb.append("- >");
        // If the condition is met, undo -> and add the result set
        if(root.left == null && root.right == null){
            sb.deleteCharAt(sb.length()-1);
            sb.deleteCharAt(sb.length()-1);
            res.add(new String(sb));
        }

        dfs(root.left , sb);
        dfs(root.right , sb);
        sb.delete(n,sb.length()); // Undo the selection to delete all additions to this turn}}Copy the code

4. Full array of strings

Leetcode-cn.com/problems/zi…

class Solution {
    public String[] permutation(String s) {
        if(s == null || s.length() == 0) return new String[0];
        List<String> list = new ArrayList<>();
        char[] chars = s.toCharArray();
        int n = chars.length;
        Arrays.sort(chars);
        boolean[] isv = new boolean[n];
        StringBuilder sb = new StringBuilder();
        dfs( sb , chars , isv ,list);
        String[] res = new String[list.size()];
        for(int i = 0 ; i < res.length ; i++){
            res[i] = list.get(i);
        }
        return res;
    }

    void dfs( StringBuilder sb , char[] chars , boolean[] isv , List<String> list){
        if(sb.length() == chars.length){
            list.add(new String(sb));
        }

        for(int i = 0 ; i < chars.length ; i++){
            if(isv[i]) continue;
            if(i > 0 && chars[i] == chars[i-1] && isv[i-1]) continue;
            sb.append(chars[i]);
            isv[i] = true;
            dfs(sb , chars , isv , list);
            sb.deleteCharAt(sb.length()-1);
            isv[i] = false; }}}Copy the code

5. The KTH permutation

Leetcode-cn.com/problems/pe…

class Solution {
    String res = "";
    int count = 1;
    public String getPermutation(int n, int k) {
        int[] nums = new int[n];
        for(int i = 0 ; i < n ; i++) nums[i] = i+1;
        boolean[] isv = new boolean[n];
        dfs(nums , k , "" , isv);
        return res;
    }

    void dfs(int[] nums , int k , String s , boolean[] isv){
        if(res ! ="") return;
        if(s.length() == nums.length){
            if(count == k) res = s;
            else count++;
        }

        for(int i = 0 ; i < nums.length ; i++){
            if(isv[i]) continue;
            s = s + nums[i];
            isv[i] = true;
            dfs(nums , k , s , isv);
            s = s.substring(0 , s.length()-1);
            isv[i] = false; }}}Copy the code

Combinatorial problems

K number combination

Leetcode-cn.com/problems/co…

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        List<Integer> list = new ArrayList<>();
        dfs(n , 1 , k , list);
        return res;
    }

    void dfs(int n , int start ,int k , List<Integer> list){
        if(list.size() == k){
            res.add(new ArrayList<>(list));
            return;
        }
			 // If n = 7 and k = 4, there is no point in starting from 55. This is because, even if 5 is selected, there are only 6 and 7, so there are only 3 candidates
      For example, n = 6, k = 4.
//path.size() == 1; //path.size() == 1; // Path.size () == 1;
// when path.size() == 2, the next number to select is 22, the starting point is 55, and the last combination to select is [5, 6];
//path.size() == 3, the next 11 numbers are selected, the starting point is at most 66, and the last combination selected is [6]

				// The upper bound of the search starting point + the number of elements to select next -1 = n
        // I <= n - (k-list.size ()) + 1 optimization
       // I <= n
        for(int i = start ; i <= n - (k - list.size()) + 1; i++){
            list.add(i);
            dfs(n , i+1 , k , list);
            list.remove(list.size()-1); }}}Copy the code

Combined total

Leetcode-cn.com/problems/co…

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] nums, int target) {
        int n = nums.length;
        if(n == 0) return res;
        List<Integer> list = new ArrayList<>();
        dfs(nums , 0 , target , list);
        return res;
    }

    void dfs(int[] nums , int start , int target,  List<Integer> list){
        if(target < 0) return;
        if(target == 0){
            res.add(new ArrayList<>(list));
            return;
        }

        for(int i = start ; i < nums.length ; i++){
            list.add(nums[i]);
            dfs(nums, i , target- nums[i] , list); // Since each number can be selected repeatedly, I remains the same
            list.remove(list.size()-1); }}}Copy the code

Sum of combinations 2

Leetcode-cn.com/problems/co…

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] nums, int target) {
        int n = nums.length;
        if(n == 0) return res;
        List<Integer> list = new ArrayList<>();
        Arrays.sort(nums);
        dfs(nums , 0 , target , list );
        return res;
    }

    void dfs(int[] nums , int start , int target , List<Integer> list ){
        if(target < 0) return;
        if(target == 0){
            res.add(new ArrayList<>(list));
            return;
        }

        for(int i = start ; i < nums.length ; i++){
            if(i > start && nums[i] == nums[i-1]) continue;
            list.add(nums[i]);
            dfs(nums , i+1 , target-nums[i] , list );
            list.remove(list.size()-1); }}}Copy the code

N Queen problem

1. Return all schemes

Leetcode-cn.com/problems/n-…

class Solution {
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        //1. Initialize the checkerboard and fill in all '.'
        List<char[]> board = new ArrayList<>();
        for(int i = 0 ; i < n ; i++){
            char[] arr = new char[n];
            Arrays.fill(arr , '. ');
            board.add(arr);
        }

        dfs(board , 0); // Start at line 0
        return res;
    }

    void dfs(List<char[]> board , int row){
        if(row == board.size()){ // End condition
            res.add(transform(board));
            return;
        }
        int n = board.size();
        for(int col = 0 ; col < n ; col++){ // iterate over each column
            if(! isValid(board , row ,col))continue; // Return if invalid
            board.get(row)[col] = 'Q'; / / to make a choice
            dfs(board , row+1); // The next line decides
            board.get(row)[col] = '. '; // Undo the current selection}}// Check whether there is any conflict in placing Q in row, col
    boolean isValid(List<char[]> board , int row , int col){
        int n = board.size();
        for(int i = 0; i < n ; i++){// Check if there are any conflicting queens in the column
            if(board.get(i)[col] == 'Q') return false;
        }
        for(int i = row-1 , j = col + 1 ; i >= 0 && j < n ; i--,j++){ // Check the upper right corner
            if(board.get(i)[j] == 'Q') return false;
        }
        for(int i = row-1 , j = col - 1 ; i >= 0 && j >= 0 ; i--,j--){ // Check the upper left
            if(board.get(i)[j] == 'Q') return false;
        }
        return true;
    }


    // Format conversion function
    List<String> transform(List<char[]> board){
        List<String> newBoard = new ArrayList<>();
        for(char[] row : board) newBoard.add(new String(row));
        returnnewBoard; }}Copy the code

2. Return the number of types of schemes

Leetcode-cn.com/problems/n-…

class Solution {
    int res = 0;
    public int totalNQueens(int n) {
        List<char[]> board = new ArrayList<>();
        for(int i = 0; i < n ; i++){char[] arr = new char[n];
            Arrays.fill(arr , '. ');
            board.add(arr);
        }
        dfs(board , 0);
        return res;
    }

    void dfs(List<char[]> board , int row){
        if(row == board.size()) res++;

        int n = board.size();
        for(int col = 0 ; col < n; col++){
            if(! isValid(board , row , col))continue;
            board.get(row)[col] = 'Q';
            dfs(board , row + 1);
            board.get(row)[col] = '. '; }}boolean isValid(List<char[]> board , int row  ,int col){
        int n = board.size();
        for(int i = 0 ; i < n ; i++){
            if(board.get(i)[col] == 'Q') return false;
        }

        for(int i = row-1 , j = col+1 ;  i >= 0 && j < n ; i--,j++){
            if(board.get(i)[j] == 'Q') return false;
        }

        for(int i = row-1 , j = col-1 ;  i >= 0 && j >=0 ; i--,j--){
            if(board.get(i)[j] == 'Q') return false;
        }
        return true; }}Copy the code

Sudoku problem

1. Determine if sudoku is valid

Leetcode-cn.com/problems/va…

class Solution {
    public boolean isValidSudoku(char[][] board) {
        for(int i = 0 ; i < board.length ; i++){
            for(int j = 0 ; j < board.length ; j++){
                if(board[i][j] == '. ') continue;
                if(! isValid(board , i , j))return false; }}return true;
    }

    private boolean isValid(char[][] board, int row, int col) {
        char c = board[row][col];
        for(int i = 0 ; i < 9 ; i++){
            if(board[i][col] == c && i ! = row)return false; // Exclude your own situation
            if(board[row][i] == c && i ! = col)return false; 
            if(board[3 * (row/3) +i/3] [3 *(col/3) + i%3] == c 
               && 3 * (row/3) +i/3! = row &&3 *(col/3) + i%3! = col)return false;
        }
        return true; }}Copy the code

2. Hard alone

Leetcode-cn.com/problems/su…

class Solution {
    public void solveSudoku(char[][] board) {
        backTrace(board , 0 , 0);
    }

    // Note that row represents the row and col represents the column.
    private boolean backTrace(char[][] board, int row, int col) {
        // Note that row starts at 0. If row is equal to board.length, it means sudoku
        // The value in sudoku is valid
        if (row == board.length)
            return true;
        // If the last column of the current row is traversed, start with the first column of the next row. The traversal here
        // The sequence is from row 1, column 1, to the last column, then row 2, column 1, to the last column
        // One column, then the third row...
        if (col == board.length)
            return backTrace(board, row + 1.0);
        // If the current position already has a number, it cannot be filled in. Go to the next column in the line
        if(board[row][col] ! ='. ')
            return backTrace(board, row, col + 1);
        // If none of the above conditions are met, we choose a suitable number from 1 to 9 to fill in the sudoku
        for (char i = '1'; i <= '9'; i++) {
            // Check whether the current position [row, col] can contain the digit I, if not, check again
            // If you can't do it from 1 to 9, you can do it
            // return false
            if(! isValid(board, row, col, i))continue;
            // If you can put the number I in, put the number I in
            board[row][col] = i;
            // If successful, return directly, no need to try again
            if (backTrace(board, row, col))
                return true;
            // Otherwise undo the reselect
            board[row][col] = '. ';
        }
        // If the current position [row, col] cannot contain any digits, return false
        return false;
    }

    // Verify that the current position [row, col] can hold the character c
    private static boolean isValid(char[][] board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            // Does the current column duplicate character c
            if (board[i][col] == c)
                return false;
            // Does the current line duplicate the character c
            if (board[row][i] == c)
                return false;
            // If there are any duplicates of character c in the current cell
            if (board[3 * (row / 3) + i / 3] [3 * (col / 3) + i % 3] == c)
                return false;
        }
        return true; }}Copy the code

Parenthesis generation problem

1. Generate all parenthesis combinations

Leetcode-cn.com/problems/ge…

class Solution {
    List<String> res = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        if(n == 0) return res;
        String s = "";
        dfs(n , n ,s); // Open and close parentheses are n
        return res;
    }

    void dfs(int l , int r , String s){
        if(l == 0 && r == 0){
            res.add(new String(s));
            return;
        }

        if(l > 0) dfs(l-1 , r , s+"("); // If the left parenthesis is greater than 0, concatenate the left parenthesis
        if(r > l) dfs(l , r-1 , s+")"); // If the number of close parentheses is greater than the number of open parentheses, concatenate the close parentheses}}Copy the code

Matrix search problem (Island problem)

1. Word search

Leetcode-cn.com/problems/wo…

class Solution {
    public boolean exist(char[][] board, String word) {
        int row = board.length;
        if(row == 0) return false;
        int col = board[0].length;
        boolean[][] isv = new boolean[row][col];
        for(int i = 0 ; i < row ; i++){
            for(int j = 0 ; j < col ; j++){
                if(board[i][j] == word.charAt(0) && dfs(board , 0 , i , j , word , isv)) return true; }}return false;
    }

    boolean dfs(char[][] board , int index , int i , int j , String word , boolean[][] isv){
        if(index == word.length()) return true;
        if(i >= board.length || i < 0 || j >= board[0].length || j < 0) return false;
        if(isv[i][j] || word.charAt(index) ! = board[i][j])return false;
        isv[i][j] = true;

        if(dfs(board , index+1 , i+1 , j ,word , isv)
          || dfs(board , index+1 , i-1 , j , word , isv)
          || dfs(board , index+1 , i , j+1 , word , isv)
          || dfs(board , index+1 , i , j-1 ,word , isv)) return true;

        isv[i][j] = false;
        return false; }}Copy the code

2. Number of islands

Leetcode-cn.com/problems/nu…

class Solution {
    public int numIslands(char[][] grid) {
        int row = grid.length;
        if(row == 0) return 0;
        int col = grid[0].length;
        int res = 0;
        for(int i = 0 ; i < row ; i++){
            for(int j = 0 ; j < col ; j++){
                if(grid[i][j] == '1'){ dfs(i , j , grid); res++; }}}return res;
    }

    void dfs(int i , int j , char[][] grid){
        if(i < 0  || i >= grid.length || j < 0 || j >= grid[0].length) return;
        if(grid[i][j] ! ='1') return;
        grid[i][j] = '0'; // Turn all adjacent ones into zeros
        dfs(i+1 , j , grid);
        dfs(i-1 , j  , grid);
        dfs(i , j+1 , grid);
        dfs(i , j-1, grid); }}Copy the code

3. Maximum area of the island

Leetcode-cn.com/problems/ma…

class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int row = grid.length;
        if(row == 0) return 0;
        int col = grid[0].length;
        int res = 0;
        for(int i = 0 ; i < row ; i++){
            for(int j = 0 ; j < col ; j++){
                if(grid[i][j] == 1){ res = Math.max(res , dfs(grid , i , j)); }}}return res;
    }

    int dfs(int[][] grid , int i , int j){
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) return 0;
        if(grid[i][j] ! =1) return 0;
        
        int count = 1;
        grid[i][j] = 2;
        count += dfs(grid , i+1 , j);
        count += dfs(grid , i , j+1);
        count += dfs(grid , i-1 , j);
        count += dfs(grid , i , j-1);
        returncount; }}Copy the code

4. Count closed islands

(leetcode-cn.com/problems/nu…).

class Solution {
    // 0 indicates land
    // 1 indicates water area
    // 2 indicates that it has been calculated
    public int closedIsland(int[][] grid) {
        int res = 0;
        for(int i = 0; i < grid.length ; i++){for(int j = 0 ; j < grid[0].length ; j++){if(grid[i][j] == 0) {if(dfs(i ,j ,grid)) // If it is a closed islandres++; }}}return res;
    }

    // Determine if the island is closed
    boolean dfs(int i , int j ,int[][] grid){
        // Closed island
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length ) return false;
        if(grid[i][j] ! =0) return true;
         grid[i][j]   = 2;
        boolean down  = dfs(i+1,j,grid);
        boolean up    = dfs(i-1,j,grid);
        boolean left  = dfs(i,j+1,grid);
        boolean right = dfs(i,j-1,grid);
        if(up && down && left && right){
            return true;
        }
        return false; }}Copy the code

5. Measure the perimeter of the island

Leetcode-cn.com/problems/is…

class Solution { public int islandPerimeter(int[][] grid) { int row = grid.length; if(row == 0) return 0; int col = grid[0].length; int res = 0; for(int i = 0 ; i < row ; i++){ for(int j = 0 ; j < col ; j++){ if(grid[i][j] == 1) { res += 4; if(i > 0 && grid[i-1][j] == 1) res -= 2; if(j > 0 && grid[i][j-1] == 1) res -= 2; } } } return res; }}Copy the code

Other classic questions

1. Alphabetic combinations of telephone numbers

Leetcode-cn.com/problems/le…

class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        if(digits.length() == 0) return res;
        Map<Character , char[]> map = new HashMap<>();
        map.put('2' , new char[] {'a' , 'b' ,'c'});
        map.put('3' , new char[] {'d' , 'e' ,'f'});
        map.put('4' , new char[] {'g' , 'h' ,'i'});
        map.put('5' , new char[] {'j' , 'k' ,'l'});
        map.put('6' , new char[] {'m' , 'n' ,'o'});
        map.put('7' , new char[] {'p' , 'q' ,'r'.'s'});
        map.put('8' , new char[] {'t' , 'u' ,'v'});
        map.put('9' , new char[] {'w' , 'x' ,'y'.'z'});
        StringBuilder sb = new StringBuilder();
        dfs(digits , 0, sb , res , map);
        return res;
    }

    void dfs(String digits ,int start ,StringBuilder sb , List<String> res ,Map<Character , char[]> map){
        // Recursive termination condition
        if(start == digits.length()){
            res.add(new String(sb));
            return;
        }

        char[] chars = map.get(digits.charAt(start));
        for(int i = 0 ; i < chars.length ; i++){
            sb.append(chars[i]);
            dfs(digits , start+1 , sb , res , map);
            sb.deleteCharAt(sb.length()-1); }}}Copy the code

2. Split palindrome strings

Leetcode-cn.com/problems/pa…

class Solution {
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> partition(String s) {
        int n = s.length();
        List<String> list = new ArrayList<>();
        dfs(s , 0 , list);
        return res;
    }

    void dfs(String s , int start , List<String> list){
        if (start == s.length()){
            res.add(new ArrayList<>(list));
            return;
        }

        for(int i = start ; i < s.length() ; i++){
            String str = s.substring(start , i+1);
            if(isHuiWen(str)){
                list.add(str);
                dfs(s , i+1 , list);
                list.remove(list.size()-1); }}}boolean isHuiWen(String s){
        int n = s.length();
        if(n == 1) return true;
        int l = 0 , r = n-1;
        while(l < r){
            if(s.charAt(l) ! = s.charAt(r))return false;
            l++;
            r--;
        }
        return true; }}Copy the code

3. Determine if it is cumulative

Leetcode-cn.com/problems/ad…

class Solution {
    public boolean isAdditiveNumber(String num) {
        int n = num.length();
        if(n < 3) return false;
        List<Long> list = new ArrayList<>();
        return dfs(num , 0 ,list);
    }
		//int may exceed the data range, so use long
    boolean dfs(String num , int start , List<Long> list){
        if(start == num.length() && list.size() > 2) return true;

        for(int i = start ; i < num.length() ; i++){
            String tem = num.substring(start , i+1);
            if(tem.charAt(0) = ='0' && tem.length() > 1) return false; // Prune: do not start with 0
            if(tem.length() > num.length()/2) return false; / / the pruning
            int size = list.size();
            if(size < 2 || Long.parseLong(tem) == list.get(size-1) + list.get(size-2)){
                list.add(Long.parseLong(tem));
                if(dfs(num , i+1 , list)) return true;
                list.remove(list.size()-1); }}return false; }}Copy the code

4. Restore the IP address

Leetcode-cn.com/problems/re…

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        int n = s.length();
        if(n == 0) return res;
        List<String> segment = new ArrayList<>();
        dfs(s , 0 ,segment, res);
        return res;
    }

    void dfs(String s , int start  , List<String> segment , List<String> res){
        if(start == s.length()){
            if(segment.size() == 4){
                StringBuilder sb = new StringBuilder();
                for(String tem : segment) sb.append(tem + ".");
                sb.deleteCharAt(sb.length()-1);
                res.add(newString(sb)); }}if(segment.size() > 4) return; // Prune if there are more than 4 segments

        for(int i = start ; i < s.length() && i < start+3 ; i++){
            String tem = s.substring(start , i+1);
            if(tem.charAt(0) = ='0' && tem.length() > 1) continue;
            int num = Integer.parseInt(tem);
            if(num <= 255 && num >= 0){
                segment.add(tem);
                dfs(s,i+1,segment ,res);
                segment.remove(segment.size()-1); }}}}Copy the code