Use "Backtracking" - an algorithm for finding all solutions by exploring all potential candidates.
class Solution {
public List<List<Integer>> permute(int[] array) {
if (array == null || array.length == 0) {
return new ArrayList();
}
List<List<Integer>> solutions = new ArrayList();
permute(array, 0, new boolean[array.length], solutions, new ArrayList());
return solutions;
}
private void permute(int[] array, int index, boolean[] used, List<List<Integer>> solutions, List<Integer> list) {
if (index == array.length) {
solutions.add(new ArrayList(list));
return;
}
for (int i = 0; i < array.length; i++) {
if (used[i] == false) {
list.add(array[i]);
used[i] = true;
permute(array, index + 1, used, solutions, list);
used[i] = false;
list.remove(list.size() - 1);
}
}
}
}If you view this recursion as a tree, there will be n! leaf nodes, so there are O(n!) nodes in total. At each node, we do O(n) work looping through the array. So our runtime is O(n * n!).
- Time Complexity: O(n * n!)
- Space Complexity: O(n * n!)