全排列permutation问题

参考链接：
字符串全排列算法学习

思路：
一位一位来固定，求后面的全排列，设当前为k位，则让[k,n]位的字符都与第k位进行交换，并且需要保证第k位不重复(代码中用set来实现)，然后对于每种情况，递归第k+1位即可。具体过程如下图：

递归的出口，就是只剩一个字符的时候。

代码如下：

import java.util.*;

public class Solution {
    public ArrayList<String> permutation(String str) {
        ArrayList<String> list = new ArrayList<>();
        if (str != null && str.length() > 0) {
            permutationHelper(str.toCharArray(), 0, list);
            Collections.sort(list);
        }
        return list;

    }

    private void permutationHelper(char[] arr, int k, ArrayList<String> list) {
        //到达最后一位，添加进list中
        if (k == arr.length - 1) {
            list.add(String.valueOf(arr));
            return;
        }

        //保存已经交换过的字符,去重
        Set<Character> set = new HashSet<>();

        for (int i = k; i < arr.length; i++) {
            if (!set.contains(arr[i])) {
                set.add(arr[i]);
                swap(arr, i, k);
                permutationHelper(arr, k + 1, list);
                swap(arr, k, i);
            }
        }
    }

    private void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}