All Permutation
出处
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Solution
选择后驱元素中的一个与当前节点交换,然后再将后面的节点作为子问题考虑。由于有重复元素,而重复元素对当前节点的影响是相同的,因此应该去重:把相同元素的替换作为同一个回溯方向/选择来处理,一旦发现是已经处理过的相同元素,则直接跳过。
或者使用 DFS 进行回溯
或者利用插入法:
P(a1) = a1
P(a1a2) = a1a2, a2a1
P(a1a2a3) = a1a2a3, a1a3a2, a2a1a3, a2a3a1, a3a1a2, a3a2a1
从第二步到第三步,恩可以看作是,对第二步中的两个结果,分别把 a3 插入到的每个结果中可能的各个位置,于是我们可以根据这个规律写出代码
Complexity
时间复杂度 O(n2 ),空间复杂度 O(n2 )
Code
插入法
public static ArrayList<String> getPermutations(String str){
if (str == null){
return null;
}
ArrayList<String> permutations = new ArrayList<String>();
if (str.length() == 0){
permutations.add("");
return permutations;
}
char first = str.charAt(0);
String rest = str.substring(1);
ArrayList<String> words = getPermutations(rest);
for (String word : words){
for (int j = 0; j <= word.length(); j++){
permutations.add(word.substring(0,j) + first + word.substring(j));
}
}
return permutations;
}
交换法
void helper(int index, ArrayList<Integer> path, ArrayList<ArrayList<Integer>> result){
if (index > path.size()) return;
if (index == path.size())
result.add(new ArrayList<Integer>(path);
HashSet<Integer> used = new HashSet<Integer>();
for (int i = index; i < path.size(); i++){
// handle duplicate
if (used.contains(path.get(i));
continue;
// make choice
swap(path, index, i);
helper(index+1, path, result);
// backtracing
swap(path, index, i);
used.put(path.get(i));
}
}
ArrayList<ArrayList<Integer>> allPermutation(ArrayList<Integer> num){
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
helper(0, num, result);
return result;
}
回溯
public class Solution {
public List<List<Integer>> permute(int[] num) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> path = new ArrayList<Integer>();
boolean[] free = new boolean[num.length];
Arrays.fill(free, true);
permuteRe(num, res, path,free);
return res;
}
void permuteRe(int[] num, List<List<Integer>> res, List<Integer> path, boolean[] free) {
if(path.size() == num.length) {
ArrayList<Integer> tmp = new ArrayList<Integer>(path);
res.add(tmp);
return;
}
for (int i = 0; i < num.length; ++i) {
if (free[i] == true) {
free[i] = false;
path.add(num[i]);
permuteRe(num, res, path, free);
path.remove(path.size() - 1);
free[i] = true;
}
}
}
}