回溯算法的理解

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

目录

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;//回溯完成，退回
        }
    }

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