从小白开始刷算法 回溯法篇 leetcode.22

序言

虽然算法很难，但不应该就放弃。这是一个学习笔记，希望你们喜欢~

先自己尝试写，大概十几分钟仍然写不出来

看思路，再尝试跟着思路写

仍然写不出来，再看视频

b站up视频推荐：爱学习的饲养员

leetcode其他文章：

数组篇：

从小白开始刷算法 数组篇 leetcode.485

从小白开始刷算法 数组篇 leetcode.283

从小白开始刷算法 数组篇 leetcode.27

链表篇：

从小白开始刷算法 ListNode 链表篇 leetcode.203

从小白开始刷算法 ListNode 链表篇 leetcode.206

队列篇

从小白开始刷算法 ListNode 链表篇 leetcode.933

栈篇

从小白开始刷算法 Stack 栈篇 leetcode.20

从小白开始刷算法 Stack 栈篇 leetcode.496

哈希篇

从小白开始刷算法 Hash 哈希篇 leetcode.217

从小白开始刷算法 Hash 哈希篇 leetcode.705

树篇

从小白开始刷算法 Tree 树篇 先序遍历 leetcode.144

从小白开始刷算法 Tree 树篇 中序遍历 leetcode.94

从小白开始刷算法 Tree 树篇 后序遍历 leetcode.94

堆篇

从小白开始刷算法 Heap 堆篇 最大堆排序 leetcode.215

小白开始刷算法 Heap 堆篇 最小堆排序 leetcode.692

双指针篇

从小白开始刷算法 对撞双指针 leetcode.881

从小白开始刷算法 快慢双指针篇 leetcode.141

二分法篇

从小白开始刷算法 二分法篇 leetcode.704

从小白开始刷算法 二分法篇 leetcode.35

从小白开始刷算法 二分法篇 leetcode.162

从小白开始刷算法 二分法篇 leetcode.74

滑动窗口篇

从小白开始刷算法 滑动窗口篇 leetcode.209

从小白开始刷算法 滑动窗口篇 leetcode.1456

递归篇

从小白开始刷算法 递归篇 leetcode.509

从小白开始刷算法 递归篇 leetcode.206

分治法篇

从小白开始刷算法 分治法篇 leetcode.169

从小白开始刷算法 分治法篇 leetcode.53

回溯法篇

难度：中等

题目：

22. 括号生成

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

示例 1：

输入：n = 3

输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]

示例 2：

输入：n = 1

输出：[“()”]

题目来源：力扣（LeetCode）

回溯法介绍

能否写出：不能写出，需要思路。

时间：50分钟多

介绍：

**回溯法（Backtracking）**是一种通过不断尝试所有可能的解空间来求解问题的算法。它常用于求解组合、排列、子集等问题。

回溯法的基本思想是通过递归的方式尝试所有可能的选择，当发现当前选择无法达到目标或者已经找到解时，进行回溯，撤销前面的选择，再尝试其他的选择，直到找到全部解或者所有可能的选择都已经尝试完。

回溯法通常包含以下步骤：

1. 定义问题的解空间：确定问题的解是什么，以及问题解的表示方式。
2. 确定选择列表：确定在当前步骤可以做出的选择，即生成下一个可能的选择列表。
3. 判断是否满足约束条件：对于生成的每个选择，判断是否满足约束条件，如果不满足，则进行回溯。
4. 处理当前选择：在满足约束条件的情况下，将当前选择加入解空间，并进行下一步递归调用。
5. 回溯：撤销当前选择，返回上一步继续尝试其他选择。

通过不断地递归调用和回溯操作，回溯法能够遍历问题的所有可能解，找到满足约束条件的解集合。

回溯法的时间复杂度通常较高，因为它需要尝试所有可能的选择。在实际应用中，通过合理的剪枝和优化策略可以降低时间复杂度。同时，回溯法的空间复杂度取决于递归调用的深度和解空间的大小。

回溯法在组合优化、排列组合、图的遍历等问题中具有广泛的应用，例如求解八皇后问题、解数独、生成括号组合等。

回溯法介绍思路：

部分思路：

如果已添加的左括号数量小于n，可以继续添加左括号，那么调用backtracking方法，在current的末尾添加一个左括号，并且open+1，close保持不变，继续递归。

如果已添加的右括号数量小于已添加的左括号数量，说明可以继续添加右括号，那么调用backtracking方法，在current的末尾添加一个右括号，并且open保持不变，close+1，继续递归。

通过不断地递归调用和回溯操作，最终会生成所有有效的括号组合，并将其存储在result中。最后，将result作为返回结果返回。

问题：

在代码中，是没有删除操作的，一开始看代码时候我还在找，后面debug发现，在回溯算法中通常不需要显式删除字符串的部分。

回溯算法的基本思想是通过递归进行深度优先搜索，在搜索的过程中通过参数的传递和回溯的特性来实现状态的回退。在字符串生成的问题中，我们可以通过传递字符串的子串或部分结果来实现状态的更新。

具体到括号生成的问题，每次递归调用时，我们可以通过在当前字符串的末尾追加"(“或”)" 来生成新的字符串，而不需要删除之前的部分。这样做的好处是节省了时间和空间，避免了在递归过程中频繁地修改和删除字符串。

例如，在括号生成的回溯算法中，我们通过传递current + "("和current + ")"来生成新的字符串，而不需要删除之前的部分。在回溯过程中，当递归返回到上一层时，current的值会回退到之前的状态，不会受到之前生成的字符的影响。

// 仅是我的思路代码，leetcode上大神更厉害
class Solution {
    public List<String> generateParenthesis(int n) {
        LinkedList<String> result = new LinkedList<>();
        backtracking(result, "", 0, 0, n);
        return result;
    }
    private void backtracking(LinkedList<String> result, String current, int open, int close, int n) {
        // 当括号数量达到上限时，将当前组合加入结果列表
        if (current.length() == 2 * n) {
            result.add(current);
            return;
        }
        // 如果左括号数量小于n，则递归添加左括号
        if (open < n) {
            backtracking(result, current + "(", open + 1, close, n);
        }
        // 如果右括号数量小于左括号数量，则递归添加右括号
        if (close < open) {
            backtracking(result, current + ")", open, close + 1, n);
        }
    }
}

时间复杂度： O(2^N * N)

每次递归调用时，都会将当前的括号组合current复制一份，并在其末尾添加一个左括号或右括号。由于每个位置都有两种选择，因此在整个递归过程中，每个位置最多被访问两次。

另外，递归的终止条件是当current的长度等于2N时，将其加入结果列表中。这个操作的时间复杂度为O(N)，因为需要将current复制一份并加入到结果列表中。

空间复杂度：O(n)

对于空间复杂度，递归调用的栈空间是主要的消耗。在最坏的情况下，递归的深度为2N，因此空间复杂度为O(N)。

同时，结果列表result存储了所有有效的括号组合，最多可能有2^N 个

组合。因此，结果列表的空间复杂度也为O(2^N)。