博客

题目：


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

例子：




总而言之，就是不带重复的排列组合。

代码1：（回溯）：

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

class Solution {
    //用来放所有可能的排列
    private List<String> list = new LinkedList();

    //将String s 转换为char[]，当作全局变量，方便调换值
    private char[] s_char;

    public String[] permutation(String s) {
        this.s_char = s.toCharArray();
        doPermutation(0);
        return list.toArray(new String[list.size()]);
    }

    private void doPermutation(int x){
        //如果到了最后一位，就终止当前递归，并添加值。
        if (x == s_char.length-1){
            list.add(String.valueOf(s_char));
            return;
        }
        //HashSet主要是防止重复的值，例如abbc，这两个b其中取一个就够了。
        HashSet<Character> set = new HashSet<>();
        for (int i = x; i < s_char.length; i++){
            //判断是否重复
            if (set.contains(s_char[i])) continue;
            set.add(s_char[i]);

            //先调换，再递归，再还原，老回溯算法了
            swap(i, x);
            doPermutation(x+1);
            swap(i, x);
        }
    }

    //调换值
    private void swap(int a, int b){
        char temp = s_char[a];
        s_char[a] = s_char[b];
        s_char[b] = temp;
    }
}

代码1解释：


回溯算法的经典思路就是改变现场，递归循环，还原现场。之前另外一道题就是树的回溯，题目是【找和为某值的树的所有路径节点】。

这个算法给出String 10个字符，返回结果90多万个排列，可怕。