回溯法

每使用一个字符就往栈中添加一个字符，如果该字符已经使用过则跳过该字符。回溯时从栈中删除字符。

class Solution { public String[] permutation(String S) { if (S.length() == 0) return new String[]{}; List<String> ans = new ArrayList<>(); Deque<Character> path = new ArrayDeque<>(); boolean[] used = new boolean[S.length()]; dfs(S, 0, used, path, ans); return ans.toArray(new String[ans.size()]); } private void dfs(String s, int depth, boolean[] used, Deque<Character> path, List<String> ans) { if (depth == s.length()) { StringBuffer buffer = new StringBuffer(); List<Character> list = new ArrayList(path); for (Character c : list) { buffer.append(c); } ans.add(buffer.toString()); } for (int i = 0; i < s.length(); i++) { if (used[i]) { continue; } path.addLast(s.charAt(i)); used[i] = true; dfs(s, depth + 1, used, path, ans); path.pollLast(); used[i] = false; } } }

回溯 交换法

依次选择每个字符与其左边字符交换，回溯时交换回原来位置

class Solution { public String[] permutation(String S) { if (S.length() == 0) return new String[]{}; List<String> ans = new ArrayList<>(); List<Character> output = new ArrayList<>(); for (int i = 0; i < S.length(); i++) { output.add(S.charAt(i)); } dfs(S.length(), 0, output, ans); return ans.toArray(new String[ans.size()]); } private void dfs(int len, int begin, List<Character> output, List<String> ans) { if (begin == len) { StringBuffer buffer = new StringBuffer(); for (Character c : output) { buffer.append(c); } ans.add(buffer.toString()); } for (int i = begin; i < len; i++) { Collections.swap(output, i, begin); dfs(len, begin + 1, output, ans); Collections.swap(output, i, begin); } } }