您好,欢迎来到12图资源库!分享精神,快乐你我!我们只是素材的搬运工!!
  • 首 页
  • 当前位置:首页 > 开发 > WEB开发 >
    450,什么叫回溯算法,一看就会,一写就废
    时间:2020-09-15 12:46 来源:网络整理 作者:网络 浏览:收藏 挑错 推荐 打印

    关于回溯算法的定义,百度百科上是这样描画的:回溯算法实践上一个相似枚举的搜索尝试进程,主要是在搜索尝试进程中寻觅成绩的解,当发现已不满足求解条件时,就“回溯”前往,尝试别的途径。回溯法是一种选优搜索法,按选优条件向前搜索,以到达目的。但当探求到某一步时,发现原先选择并不优或达不到目的,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个形状的点称为“回溯点”。许多复杂的,规模较大的成绩都可以运用回溯法,有“通用解题办法”的美称。

    看明白没,回溯算法其实就是一个不断探求尝试的进程,探求成功了也就成功了,探求失败了就在退一步,继续尝试……,

    组合总和

    组合总和算是一道比较经典的回溯算法题,其中有一道题是这样的。

    找出一切相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。

    阐明:

    一切数字都是正整数。

    解集不能包含重复的组合。

    示例 1:

    输入: k = 3, n = 7

    输入: [[1,2,4]]

    示例 2:

    输入: k = 3, n = 9

    输入: [[1,2,6], [1,3,5], [2,3,4]]

    这题说的很明白,就是从1-9中选出k个数字,他们的和等于n,并且这k个数字不能有重复的。所以第一次选择的时分可以从这9个数字中任选一个,沿着这个分支走下去,第二次选择的时分还可以从这9个数字中任选一个,但由于不能有重复的,所以要扫除第一次选择的,第二次选择的时分只能从剩下的8个数字中选一个……。这个选择的进程就比较阴暗了,我们可以把它看做一棵9叉树,除叶子结点外每个节点都有9个子节点,也就是下面这样

    450,什么叫回溯算法,一看就会,一写就废

    从9个数字中任选一个,就是沿着他的任一个分支不断走下去,其实就是DFS(假设不懂DFS的可以看下373,数据结构-6,树),二叉树的DFS代码是下面这样的

    public static void treeDFS(TreeNode root) { 

        if (root == null

            return

        System.out.println(root.val); 

        treeDFS(root.left);    treeDFS(root.right);} 

    这里可以仿照二叉树的DFS来写一下9叉树,9叉树的DFS就是经过递归遍历他的9个子节点,代码如下

    public static void treeDFS(TreeNode root) { 

        //递归必需要有终止条件 

        if (root == null

            return

        System.out.println(root.val);    //经过循环,辨别遍历9个子树 

        for (int i = 1; i <= 9; i++) { 

            //2,一些操作,可有可无,视状况而定 

            treeDFS("第i个子节点"); 

            //3,一些操作,可有可无,视状况而定 

        }} 

    DFS其实就相当于遍历他的一切分支,就是列出他一切的能够结果,只需判别结果等于n就是我们要找的,那么这棵9叉树最多有多少层呢,由于有k个数字,所以最多只能有k层。来看下代码

    public List<List<Integer>> combinationSum3(int k, int n) { 

        List<List<Integer>> res = new ArrayList<>(); 

        dfs(res, new ArrayList<>(), k, 1, n); 

        return res; 

    }private void dfs(List<List<Integer>> res, List<Integer> list, int k, int start, int n) { 

        //终止条件,假设满足这个条件,再往下找也没什么意义了 

        if (list.size() == k || n <= 0) { 

            //假设找到一组适宜的就把他参加到集合list中 

            if (list.size() == k && n == 0) 

                res.add(new ArrayList<>(list)); 

            return

        } 

        //经过循环,辨别遍历9个子树 

        for (int i = start; i <= 9; i++) { 

            //选择以后值 

            list.add(i); 

            //递归 

            dfs(res, list, k, i + 1, n - i); 

            //撤销选择 

            list.remove(list.size() - 1); 

        } 

    代码相对来说还是比较复杂的,我们来剖析下(假设看懂了可以直接跳过)。

    代码dfs中最末尾的中央是终止条件的判别,之前在426,什么是递归,经过这篇文章,让你彻底搞懂递归中讲过,递归必需要有终止条件。

    (责任编辑:admin)