回溯算法基本思想

回溯算法是系统地搜索问题的解的方法。 某个问题的所有可能解的称为问题的解空间，若解空间是有限的,则可将解空间映射成树结构。 任何解空间可以映射成树结构的问题，都可以使用回溯法。 回溯法是能够在树结构里搜索到通往特定终点的一条或者多条特定路径。 回溯算法的基本思想是：从一条路往前走,能进则进，不能进则退回来，换-条路再试，从而搜索到抵达特定终点的一条或者多 条特定路径。 值得注意，回溯法以深度优先搜索的方式搜索解空间,诅在搜索过程中用剪枝函数避免无效搜索。

深度优先算法基本思想

深度度优先搜索的能够在图结构里搜索到通往特定终点的一条或者多条特定路径。每条路深入到不能再深入，并且每条个点只访问一次;属于盲目搜索,最糟糕的情况算法时间复杂度为O(n!)。

回溯算法和深度优先算法的区别是？

可以浅显地认为回溯=深度优先+剪枝函数

但是两者却又存在不同，就是深度优先算法适用于所有的图但是回溯只适合于树结构

例题

1. 有效的括号组合

题目描述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 示例： 输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]

解题思路

对于这题，首先我们知道他需要我们找到所有的可能；并且这里是需要得到所有的组合，那试想一下我们学数据结构的时候是不是学过一种结构----树，可以列出我们所有的可能性，那么，我们就可以使用回溯的方法进行求解了

public class Solution {

    // 做减法

    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        // 特判
        if (n == 0) {
            return res;
        }

        // 执行深度优先遍历，搜索可能的结果
        dfs("", n, n, res);
        return res;
    }

    /**
     * @param curStr 当前递归得到的结果
     * @param left   左括号还有几个可以使用
     * @param right  右括号还有几个可以使用
     * @param res    结果集
     */
    private void dfs(String curStr, int left, int right, List<String> res) {
        // 因为每一次尝试，都使用新的字符串变量，所以无需回溯
        // 在递归终止的时候，直接把它添加到结果集即可，注意与「力扣」第 46 题、第 39 题区分
        if (left == 0 && right == 0) {
            res.add(curStr);
            return;
        }

        // 剪枝（如图，左括号可以使用的个数严格大于右括号可以使用的个数，才剪枝，注意这个细节）
        if (left > right) {
            return;
        }

        if (left > 0) {
            dfs(curStr + "(", left - 1, right, res);
        }

        if (right > 0) {
            dfs(curStr + ")", left, right - 1, res);
        }
    }
}