首页 > 编程语言 > 详细

算法 - 回溯算法

时间:2020-10-18 12:25:10      阅读:31      评论:0      收藏:0      [点我收藏+]

必看解析

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

2-回溯算法详解(修订版)

 

回溯算法的框架:

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

 

 

必看例子

Attention: 注意“全排列”和“所有子集”中backtrack()的参数区别。

  • “所有子集”中有一个start参数,代表遍历到了哪里,不走回头路,是为了防止重复
  • “全排列”本身就是各种元素的排序,元素肯定是重复的,所有就没有这个start参数,索引始终从0开始。

 

全排列

LeetCode 46 - 全排列  

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        //暂存结果
        ArrayList<Integer> track = new ArrayList<>();
        //最终结果
        List<List<Integer>> result = new ArrayList<>();
        //回溯函数
        backtrack(nums, track, result);
        return result;
    }

    private void backtrack(int[] nums, ArrayList<Integer> track, List<List<Integer>> result){
        //end condition
        if(track.size() == nums.length){
            result.add(new ArrayList(track));
            return;
        }

        //【重要】每次索引都从0开始!!!这里和“所有子集”问题不同
        for(int i = 0; i < nums.length; i++){
            //用contains判断是否存在
            if(! track.contains(nums[i])){
                track.add(nums[i]);
                backtrack(nums, track, result);
                //删除容器里,最后一个索引的值
                track.remove(track.size()-1);
            }
        }
    }
}

 

 

所有子集

Leetcode 78 - 子集

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> track = new ArrayList<>();

        backtrack(nums, 0, track, res);

        return res;

    }

//【重要】注意这个参数start private void backtrack(int[] nums, int start, List<Integer> track, List<List<Integer>> res){ //每一个路径,都是一个解 //【重要】这里没有明显的一个递归出口,而是靠下面的for循环的终止条件 //【重要】因为track是公用的,所以在加入res前,需要复制一份新的 res.add(new ArrayList(track));
//每次递归不是从0开始,而是start for(int i = start; i < nums.length; i++){ //重要】i 已经放在了track暂时解中,因此在此前提下,之后的递归就要exclude这个i,那就i+1即可 track.add(nums[i]); //System.out.println("track add " + nums[i]); backtrack(nums, i+1, track, res); track.remove(track.size() - 1); } } }

 

算法 - 回溯算法

原文:https://www.cnblogs.com/frankcui/p/13833204.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!