# Three Solutions in Java (Both recursive and iterative)

• Solution 1: Backtracking, Recursive. Store index instead of value in path to avoid picking the used candidate.

``````public class Solution {
List<List<Integer>> permute(int[] a) {
List<List<Integer>> result = new ArrayList<>();
if (a == null || a.length == 0) return result;
Arrays.sort(a);
backtrack(a, result, new ArrayList<>());
return result;
}

void backtrack(int[] a, List<List<Integer>> result, List<Integer> path) {
if (path.size() == a.length) {
List<Integer> real = new ArrayList<>();
for (int idx : path) real.add(a[idx]);
return;
}

for (int i = 0; i < a.length; i++) {
if (!path.contains(i)) {
backtrack(a, result, path);
path.remove(path.size() - 1);
while (i + 1 < a.length && a[i + 1] == a[i]) i++;
}
}
}
}
``````

Solution 2: DP (DFS), iterative. Using two result to backup each other.

``````public class Solution {
List<List<Integer>> permute3(int[] a) {
List<List<Integer>> result = new ArrayList<>();
if (a == null || a.length == 0) return result;
for (int round : a) {
List<List<Integer>> temp = new ArrayList<>();
for (List<Integer> path : result) {
for (int pos = 0; pos <= path.size(); pos++) {
if (pos > 0 && path.get(pos - 1) == round) break;
List<Integer> newpath = new ArrayList<>(path);
}
}
result = temp;
}
return result;
}
}
``````

Solution 3: DP (DFS), iterative. Using queue to update result set in each round.

``````public class Solution {
public List<List<Integer>> permuteUnique(int[] a) {
if (a == null || a.length == 0) return result;
for (int round : a) {
int size = result.size();
for (int i = 0; i < size; i++) {
List<Integer> path = result.remove();
for (int pos = 0; pos <= path.size(); pos++) {
if (pos > 0 && path.get(pos - 1) == round) break;
List<Integer> newpath = new ArrayList<>(path);