回溯

---

46. 全排列

// 全排列的长度固定，需要flag标记
class Solution {
    private List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> permute(int[] nums) {
        boolean[] flag = new boolean[nums.length];
        traceBack(nums, 0, flag, new ArrayList<>(nums.length));

        return ans;
    }

    public void traceBack(int[] nums, int depth, boolean[] flag, List<Integer> temp) {
        if (depth == nums.length) {
            ans.add(new ArrayList<>(temp));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (flag[i]) continue;
            flag[i] = true;
            temp.add(nums[i]);
            traceBack(nums, depth + 1, flag, temp);
            flag[i] = false;
            temp.remove(temp.size() - 1);
        }
    }
}

78. 子集

// 子集遍历了所有的路径，感觉这题还是很重要的
// 输入：nums = [1,2,3]
// 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
class Solution {
    private List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        traceBack(nums, 0, new ArrayList<Integer>());
        return ans;
    }

    public void traceBack(int[] nums, int start, List<Integer> path) {
        ans.add(new ArrayList(path));
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            traceBack(nums, i + 1, path);
            path.remove(path.size() - 1);
        }
    }
}

17. 电话号码的字母组合

class Solution {
    private List<String> ans = new ArrayList<>();
    private String[] button = new String[] { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

    public List<String> letterCombinations(String digits) {
        if (digits.length() != 0) {
            dfs(digits, 0, new char[digits.length()]);
        }
        return ans;
    }

    public void dfs(String digits, int depth, char[] letter) {
        if (depth == digits.length()) {
            ans.add(new String(letter));
            return;
        }
        int num = digits.charAt(depth) - '0';
        String curstr = button[num];
        for (int i = 0; i < curstr.length(); i++) {
            letter[depth] = curstr.charAt(i);
            dfs(digits, depth + 1, letter);
        }
    }
}

39. 组合总和

// 看题目条件都是比较小的正数，超出范围即可return
// 本题允许重复，下一层的start从i开始
class Solution {
    private List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        traceBack(candidates, target, 0, 0, new ArrayList<Integer>());
        return ans;
    }

    public void traceBack(int[] candidates, int target, int start, int curSum, List<Integer> path) {
        if (curSum == target) {
            ans.add(new ArrayList<Integer>(path));
            return;
        } else if (curSum > target) {
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            // curSum += candidates[i]; 这里可以简化，往下传递的加上即可
            path.add(candidates[i]);
            traceBack(candidates, target, i, curSum + candidates[i], path);
            // curSum -= candidates[i];
            path.remove(path.size() - 1);
        }
    }
}

22. 括号生成

// 使用字符数组即可，简单的回溯，当前层l + r直接覆盖下标元素即可
class Solution {
    List<String> ans = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        dfs(n, 0, 0, new char[n * 2]);
        return ans;
    }

    public void dfs(int n, int l, int r, char[] temp) {
        if (l < r || l > n) {
            return;
        }
        if (l + r == n * 2) {
            ans.add(new String(temp));
            return;
        }
        temp[l + r] = '(';
        dfs(n, l + 1, r, temp);
        temp[l + r] = ')';
        dfs(n, l, r + 1, temp);
    }
}

79. 单词搜索

// 回溯即可，需要深度，最好有返回值剪枝终止
// 考虑仅包含英文字母，为了省去flag的空间，直接在原数组中用空格标记，word字符串还原
class Solution {
    public boolean exist(char[][] board, String word) {
        for (int x = 0; x < board.length; x++) {
            for (int y = 0; y < board[0].length; y++) {
                if (dfs(board, word, x, y, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] board, String word, int x, int y, int depth) {
        if (depth == word.length()) {
            return true;
        }
        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length) {
            return false;
        }
        // 题目给定条件是大小写英文字符，经过的点设为空格合理
        if (board[x][y] != word.charAt(depth)) {
            return false;
        }
        // 匹配才能进入下层递归，还原可以用word对应位置字符
        board[x][y] = ' ';
        boolean res = dfs(board, word, x - 1, y, depth + 1) ||
                dfs(board, word, x + 1, y, depth + 1) ||
                dfs(board, word, x, y - 1, depth + 1) ||
                dfs(board, word, x, y + 1, depth + 1);
        board[x][y] = word.charAt(depth);
        return res;
    }
}

131. 分割回文串

// 注意题目条件是，每个子串都是回文子串，将判断是否是回文抽离出来
class Solution {
    private List<List<String>> ans = new ArrayList<>();

    public List<List<String>> partition(String s) {
        dfs(s, 0, new ArrayList<String>());
        return ans;
    }

    public void dfs(String s, int start, List<String> path) {
        if (start == s.length()) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int end = start; end < s.length(); end++) {
            // s[start, end]不是回文, continue
            if (!isABA(s, start, end)) {
                continue;
            }
            path.add(s.substring(start, end + 1));
            dfs(s, end + 1, path);
            path.remove(path.size() - 1);
        }
    }

    public boolean isABA(String s, int start, int end) {
        while (start < end) {
            if (s.charAt(start++) != s.charAt(end--)) {
                return false;
            }
        }
        return true;
    }
}

51. N 皇后

class Solution {
    List<List<String>> ans;
    int[][] matrix;
    
    public void killPath(int x, int y, int add, int n){
        matrix[x][y] -= add;
        for(int i = 0; i < n; i++){
            matrix[i][y] += add;
            matrix[x][i] += add;
        }
        for(int i = x - 1, j = y - 1; i >= 0 && j >= 0; i--, j--){
            matrix[i][j] += add;
        }
        for(int i = x + 1, j = y + 1; i < n && j < n; i++, j++){
            matrix[i][j] += add;
        }
        for(int i = x - 1, j = y + 1; i >= 0 && j < n; i--, j++){
            matrix[i][j] += add;
        }
        for(int i = x + 1, j = y - 1; i < n && j >= 0; i++, j--){
            matrix[i][j] += add;
        }
    }

    public void traceBack(int depth, int n){
        if(depth == n){
            //记录结果
            List<String> res = new ArrayList<>(n);
            for(int i = 0; i < n; i++){
                char[] s = new char[n];
                for(int j = 0; j < n; j++){
                    s[j] = matrix[i][j] == 1 ? 'Q' : '.';
                }
                res.add(new String(s));
            }
            ans.add(res);
            return;
        }
        for(int i = 0; i < n; i++){
            if(matrix[depth][i] > 0) continue;
            //四个方向进行标记
            killPath(depth, i, 1, n);
            traceBack(depth+1, n);
            //四个方向标记解除
            killPath(depth, i, -1, n);
        }
    }
    
    public List<List<String>> solveNQueens(int n) {
        ans = new ArrayList();
        matrix = new int[n][n];

        traceBack(0, n);
        return ans;
    }
}