刷题日志--回溯 5.5

括号生成

来源：力扣（Leetcode）
链接：https://leetcode.cn/problems/IDBivT/

问题叙述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。

示例 1

输入

n = 3

输出

[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]

示例 2

输入

n = 1

输出

[“()”]

提示

1 <= n <= 8

分析

给你N对括号，如果能正确拼出括号序列的话，需要满足，从左往右遍历时，左括号的个数要大于右括号的个数。相反的，如果从左往右遍历时，发现左括号的个数少于右括号的个数，那么一定不能拼出正确的括号序列(自己脑补一下两个左括号，三个右括号)。

下面的代码我是按剩余括号个数算的

剪枝条件就是：剩余的左括号个数大于右括号个数。
达成条件是：剩余左右括号个数都为0，即用完了。

Code

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList();
        if (n == 0) return res;
        dfs("", n, n, res);
        return res;
    }

    static void dfs(String str, int left, int right, List<String> res) {
        if (left > right) return;
        if (left == 0 && right == 0) {
            res.add(str);
            return;
        }
        if (left > 0) dfs(str + "(", left - 1, right, res);
        if (right > 0) dfs(str + ")", left, right - 1, res);
    }
}

路径总和II

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum-ii

问题叙述

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。

叶子节点是指没有子节点的节点。

示例 1

输入

root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22

输出

[[5,4,11,2],[5,8,4,5]]

示例 2

输入

root = [1,2,3], targetSum = 5

输出

[]

示例 3

输入

root = [1,2], targetSum = 0

输出

[]

提示

树中节点总数在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

Code

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        backTrack(root, targetSum);
        return res;
    }

    void backTrack(TreeNode root, int targetSum) {
        if (root == null) return;
        path.add(root.val);
        targetSum -= root.val;
        if (root.left == null && root.right == null && targetSum == 0)
            res.add(new ArrayList<>(path));
        backTrack(root.left, targetSum);
        backTrack(root.right, targetSum);
        path.removeLast();
    }
}

二叉树的所有路径

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-paths

问题叙述

给你一个二叉树的根节点 root ，按任意顺序，返回所有从根节点到叶子节点的路径。

叶子节点是指没有子节点的节点。

示例 1

输入

root = [1,2,3,null,5]

输出

[“1->2->5”,“1->3”]

示例 2

输入

root = [1]

输出

[“1”]

提示

树中节点的数目在范围 [1, 100] 内
-100 <= Node.val <= 100

分析

Code

class Solution {
    List<String> res = new ArrayList<>();

    public List<String> binaryTreePaths(TreeNode root) {
        backTrack("", root);
        return res;
    }

    void backTrack(String str, TreeNode root) {
        if (root == null) return;
        StringBuffer sb = new StringBuffer(str);
        sb.append(root.val);
        if (root.left == null && root.right == null)
            res.add(sb.toString());
        else {
            sb.append("->");
            backTrack(sb.toString(), root.left);
            backTrack(sb.toString(), root.right);
        }
    }
}

优美的排列

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/beautiful-arrangement

问题叙述

假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm（下标从 1 开始），只要满足下述条件之一，该数组就是一个优美的排列：

perm[i] 能够被 i 整除
i 能够被 perm[i] 整除
给你一个整数 n ，返回可以构造的优美排列的数量。

示例 1

输入

n = 2

输出

解释

第 1 个优美的排列是 [1,2]：

perm[1] = 1 能被 i = 1 整除
perm[2] = 2 能被 i = 2 整除

第 2 个优美的排列是 [2,1]:

perm[1] = 2 能被 i = 1 整除
i = 2 能被 perm[2] = 1 整除

示例 2

输入

n = 1

输出

提示

1 <= n <= 15

分析

有约束条件的全排列问题

Code

class Solution {
    int res = 0;

    public int countArrangement(int n) {
        backTrack(n, 1, new boolean[n + 1]);
        return res;
    }

    void backTrack(int n, int index, boolean[] visited) {
        if (index > n) res++;
        for (int i = 1; i <= n; i++) {
            if (!visited[i] && (i % index == 0 || index % i == 0)) {
                visited[i] = true;
                backTrack(n, index + 1, visited);
                visited[i] = false;
            }
        }
    }
}