字符串的全排列（回溯）_字符串全排列 - 回溯

    List<String> res = new ArrayList<>();
    char []c;
    
    public String[] permutation(String s) {
        c = s.toCharArray();
        change(0);
        return res.toArray(new String[res.size()]);
    }

    public void change(int x){
        // x 表示现在本次固定的位数
        if(x==c.length-1){
            res.add(String.valueOf(c));
            return;
        }
        Set<Character> set = new HashSet<>();
        for(int i = x;i<c.length;i++){
            if(set.contains(c[i])) continue;
            set.add(c[i]);
            //交换位置
            swap(i,x);
            //递归固定下一位
            change(x+1);
            //再交换回来
            swap(i,x);
        }

    }

    public void swap(int a,int b){
        char temp = c[a];
        c[a] = c[b];
        c[b] = temp;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

res.toArray(new String[res.size()]); 表示把List res 转化为一个字符串数组

set是为了防止一层中有重复字符出现 例如abb 只能出现一次

res.add(String.valueOf©); 把字符数组转化为字符串

--------------------------------------------------------------------------------

例如"abc"

开始x=0 i=0 交换a a 递归进入下一层 x=1 i=1 交换bb 递归进入x=2 此时满足x = c.length-1 把c中的abc加入res 退出x=2这层的递归 交换回bb

此时x=1 i=2 交换bc c数组中的字符变为acb 递归进入 x=2 递归终止 把acb加入res 返回x=1层的递归 交换回b c

此时 x=1 i=3 不满足for循环 退到x=0层递归 此时 x=0 i=1 交换ab的位置 c中的元素变为 bac 依次类推