Java教程

回溯算法的理解

本文主要是介绍回溯算法的理解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录

1、思路

2、例子


1、思路

看过很多回答,知道他们回答的意思,可是又感觉有些地方将的不太清楚,于是重新回溯了这个过程。更加认识到回溯。回溯大概理解就是:有两条路,这条路走到终点,然后回到岔路口,重新走另外一条路。

下面来看一段回溯代码

        int[] nums;
        for (int i = 0; i < nums.length; i++) {
            path.add(nums[i]);
            System.out.println("回溯之前"+path);
            permuteHelper(nums);//调用
            path.removeLast();//回溯
            used[i] = false;
            System.out.println("回溯之后"+path);
            //System.out.println(used[i]);

        }

得到的部分结果

可以看见,在到达结尾后,就自动退回到上一步,然后进行下一次,依次进行,直到全部结束。

2、例子

在知道什么是回溯以后,我们可以对所有的回溯进行选择,得到我们想要的答案

因此有题目全排列

给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

我们想要的是所有不重复的选择的答案,可以构造一个选择一个数后为true,true的时候,表示该数用过,不能选择。

有代码

    List<List<Integer>> l = new ArrayList<>();
    List<Integer> res = new ArrayList<>();
    boolean[] flag;

    public List<List<Integer>> permute(int[] nums) {
        if (nums == null) return null;
        int length = nums.length;
        flag = new boolean[length];
        permuteHelper(nums);
        return l;

    }

    private void permuteHelper(int[] nums) {
        if (nums.length == res.size()) {
            l.add(new ArrayList<>(res));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (flag[i]) {//条件
                continue;
            }
            flag[i] = true;
            res.add(nums[i]);
            permuteHelper(nums);
            res.remove(res.size()-1);
            flag[i] = false;//回溯完成,退回
        }
    }

这篇关于回溯算法的理解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!