Word search

The title

Version 1 is correct

    boolean [][] visited;
    public boolean exist(char[][] board, String word) {

        // 单词搜索
        // 先按行遍历, 寻找到和word第一个字符相同的位置, 然后作为起点, 开始回溯
        // 对board中, 所有和word第一个字符相同的位置, 进行一次回溯, 任何一个位置为true, 则结果为true
        visited = new boolean[board.length][board[0].length];

        for (int i = 0; i < board.length; i ++) {
            for (int j = 0; j < board[0].length; j ++) {
                if (board[i][j] == word.charAt(0)) {
                    // 回溯一次
                    boolean flag = backtrack(board, word, new int []{i, j}, 0);
                    if (flag) {
                        return flag;
                    }
                }
            }
        }

        return Boolean.FALSE;


    }

    public boolean backtrack(char [][] board, String word, int [] position, int k) {
        // 判断word的第k个字符是否和board当前位置的字符相同
        if (word.charAt(k) != board[position[0]][position[1]]) {
            return Boolean.FALSE;
        }

        if (k == word.length() - 1) {
            return Boolean.TRUE;
        }

        // 注意是标记当前位置为true, 来不走回头路
        visited[position[0]][position[1]] = Boolean.TRUE;
        // 回溯
        int [][] choices = {{0 , 1}, {0, -1}, {1, 0}, {-1, 0}};
        for (int i = 0; i < choices.length; i ++) {
            int [] choice = choices[i];
            int targetRow = choice[0] + position[0];
            int targetCol = choice[1] + position[1];
            if (targetRow < 0 || targetRow >= board.length || targetCol < 0 || targetCol >= board[0].length || visited[targetRow][targetCol]) {
                continue;
            }

            // 做出选择
            boolean flag = backtrack(board, word, new int[] {targetRow, targetCol}, k + 1);
            if (flag) {
                return flag;
            }
        }
        // 撤销当前位置的选择
        visited[position[0]][position[1]] = Boolean.FALSE;

        return Boolean.FALSE;
    }
Copy the code

The right reason

(1) Notice whether the recursion can continue at the beginning of the recursive function

(2) Then, before making a selection, mark the current location as visited, each time marking the current location instead of marking the selected location

Goals and

The title

Version 1 is correct

int ans; Public int findTargetSumWays(int[] nums, int target) {public int findTargetSumWays(int[] nums, int target) { Backtrack (nums, target, 0L, 0); return ans; } public void backtrack(int [] nums, int target, long tempSum, int start) { if (start == nums.length) { if (tempSum == target) { ans ++; } return; } for (int i = 0; i < 2; Backtrack (nums, target, tempSum + nums[start], start + 1); backtrack(nums, target, tempSum + nums[start], start + 1); Backtrack (nums, target, tempSum - nums[start], start + 1); backtrack(nums, target, tempSum - nums[start], start + 1); }}}Copy the code

The right reason

(1) Using backtracking, enumerate the cases in which each number selected a plus or minus sign

(2) The following statement is incorrect because it does not count the sum of the elements of the array whose length is exactly the sum of the elements of the array. If we assume that the array is [1, 1, 1] and start = 2, we recurse to the next level, and start = 3, and ans is not counted

    if (start == nums.length) {
        return;
    }

    if (tempSum == target) {
        ans ++;
    }
Copy the code