回溯法求排列组合问题
这题说了是存在重复字符的,要处理一下
public ArrayList<String> permutation(String str) {
ArrayList<String> res = new ArrayList<>();
String[] strings = str.split("");
int length = strings.length;
boolean[] used = new boolean[length];
Arrays.sort(strings);
permutationBackTrace(strings, length, used, 0, new ArrayList<>(), res);
return res;
}
//递归开始
public void permutationBackTrace(String[] strs, int length, boolean[] used, int start, List<String> path, List<String> res) {
if (start == length) {
res.add(String.join("", path));
return;
}
for (int i = 0; i < strs.length; i++) {
//精华部分,需要好好理解一下,自己调试一下看看,嘿嘿嘿
'if (used[i] || (i > 0 && strs[i].equals(strs[i - 1]) && !used[i-1])) continue;'
//其他部分就很容易理解了,自己看看
path.add(strs[i]);
used[i] = true;//
permutationBackTrace(strs, length, used, start + 1, path, res);
used[i] = false;
path.remove(path.size() - 1);
}
}