# Concise O(n! * n) Java solution.

• The idea is to use the input array to store the current result.
In every iteration the ith element is fixed.
I.e. in our first call to the recursive permute function we swap all the elements into the first place once.

``````public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
permute(nums, 0, result);
return result;
}

private void permute(int[] nums, int curr, List<List<Integer>> result) {
if (curr == nums.length) {
List<Integer> res = new ArrayList<>();
for (int num: nums) {
}
}

for (int i = curr; i < nums.length; i++) {
swap(nums, curr, i);
permute(nums, curr + 1, result);
swap(nums, curr, i);
}
}

private void swap(int[] nums, int i1, int i2) {
int tmp = nums[i1];
nums[i1] = nums[i2];
nums[i2] = tmp;
}
``````

• This post is deleted!

• @zhongyuliu0517-gmail-com yes but O(n^n) is not

• Can you point out some "O(n^n)" solutions?

(Edit: I asked because the original title here was "Concise O(n!) Java solution (lots of solutions are O(n^n))")

• @devggg Aren't those two O(n! · n2) and O(n! · n), respectively? And yours isn't O(n!) but only O(n! · n) as well, since you copy the array at the bottom level.

• @StefanPochmann You are right my answer is O(n! * n). I did not account for the copying of the array.
Wow while writing this answer I understood why my assumption was false. Thank you for pointing that out. The remaing question is if this code (2nd link):

``````for (int i = 0; i < numLength; i++) {
if (!isUsed[i]) {
isUsed[i] = true;
doPermutation(index + 1, num);
isUsed[i] = false;
al.remove(index);
}
}
``````

Has a negative impact on the running time. Since on each recursive call the whole array is traversed.

• on each recursive call the whole array is traversed.

Yes, but it doesn't change the number of recursive calls. It just adds one global factor n. Except for the base case, so it's not two extra n but only one.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.