回溯算法解题模板

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

1，回溯算法解决
字符串的排列其实就是排列组合，我们可以把它想象成为一棵n叉树（n是s的长度），然后每一个节点都要从字符串中选择一个字符，但注意不能选择重复的，比如在一个节点选择了a，那么他的子孙节点都不能再选择a了

作者：sdwwld
链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/solution/shu-ju-jie-gou-he-suan-fa-hui-su-suan-fa-11gk/
来源：力扣（LeetCode）

java

private void backtrack("原始参数") {
    //终止条件(递归必须要有终止条件)
    if ("终止条件") {
        //一些逻辑操作（可有可无，视情况而定）
        return;
    }

    for (int i = "for循环开始的参数"; i < "for循环结束的参数"; i++) {
        //一些逻辑操作（可有可无，视情况而定）

        //做出选择

        //递归
        backtrack("新的参数");
        //一些逻辑操作（可有可无，视情况而定）

        //撤销选择
    }
}

入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:

输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]

这里只需要按照这个模板对他稍作修改即可，代码如下

public String[] permutation(String s) {
    Set<String> res = new HashSet<>();
    backtrack(s.toCharArray(), "", new boolean[s.length()], res);
    return res.toArray(new String[res.size()]);
}

private void backtrack(char[] chars, String temp, boolean[] visited, Set<String> res) {
    //边界条件判断，当选择的字符长度等于原字符串长度的时候，说明原字符串的字符都已经
    //选完了
    if (temp.length() == chars.length) {
        res.add(temp);
        return;
    }
    //每一个节点我们都要从头开始选
    for (int i = 0; i < chars.length; i++) {
        //已经选择过的就不能再选了
        if (visited[i])
            continue;
        //表示选择当前字符
        visited[i] = true;
        //把当前字符选择后，到树的下一层继续选
        backtrack(chars, temp + chars[i], visited, res);
        //递归往回走的时候要撤销选择
        visited[i] = false;
    }
}

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