# All Permutation

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

## Solution

P(a1) = a1

P(a1a2) = a1a2, a2a1

P(a1a2a3) = a1a2a3, a1a3a2, a2a1a3, a2a3a1, a3a1a2, a3a2a1

## Code

public static ArrayList<String> getPermutations(String str){
if (str == null){
return null;
}

ArrayList<String> permutations = new ArrayList<String>();
if (str.length() == 0){
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++){
}
}
return permutations;
}

void helper(int index, ArrayList<Integer> path, ArrayList<ArrayList<Integer>> result){
if (index > path.size()) return;

if (index == path.size())

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);