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

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

示例:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

递归

import java.util.*;

class Solution {
    private List<String> ans = new ArrayList<>();

    private LinkedList<Character> path = new LinkedList<>();

    private void add() {
        StringBuilder sb = new StringBuilder();
        for (Character c : path) {
            sb.append(c);
        }
        ans.add(sb.toString());
    }

    private void solve(char[] str, int index, boolean[] visited) {
        if (index == str.length) {
            add();
            return;
        }
        for (int i = 0; i < str.length; ++i) {
            if (!visited[i] && !(i > 0 && !visited[i - 1] && str[i] == str[i - 1])) {
                path.offerLast(str[i]);
                visited[i] = true;
                solve(str, index + 1, visited);
                visited[i] = false;
                path.pollLast();
            }
        }
    }

    public String[] permutation(String s) {
        if (s == null || s.length() == 0) {
            return new String[0];
        }
        char[] str = s.toCharArray();
        Arrays.sort(str);
        solve(str, 0, new boolean[str.length]);
        return ans.toArray(new String[0]);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String[] permutations = new Solution().permutation(in.next());
            Arrays.stream(permutations).forEach(System.out::println);
        }
    }
}

迭代

import java.util.*;

class Solution {

    private boolean end(char[] str, char[] end) {
        for (int i = 0; i < str.length; ++i) {
            if (str[i] != end[i]) {
                return false;
            }
        }
        return true;
    }

    private void swap(char[] str, int a, int b) {
        char t = str[a];
        str[a] = str[b];
        str[b] = t;
    }

    private void reverse(char[] str, int left, int right) {
        while (left < right) {
            swap(str, left++, right--);
        }
    }

    private void next(char[] str) {
        int i = str.length - 2;
        while (i >= 0 && str[i] >= str[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = str.length - 1;
            while (str[i] >= str[j]) {
                j--;
            }
            swap(str, i, j);
        }
        reverse(str, i + 1, str.length - 1);
    }

    public String[] permutation(String s) {
        List<String> ans = new ArrayList<>();
        char[] str = s.toCharArray();
        do {
            ans.add(new String(str));
            next(str);
        } while (!end(str, s.toCharArray()));
        return ans.toArray(new String[0]);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String[] permutations = new Solution().permutation(in.next());
            Arrays.stream(permutations).forEach(System.out::println);
        }
    }
}