46. Permutations

Summary

Given an array nums of distinct integers, return all possible permutations. You can return the answer in any order.

Constraints:

1 <= nums.length <= 6
-10 <= nums[i] <= 10

Approach

Let's use backtracking.

Function

Initialization:

permutations = []

Recursion:

Arguments:

used, the set of numbers already used in the current permutation.
comb, the current permutation being built.

If the length of comb is equal to the length of nums, we have found one permutation. Create a copy of comb, add it to permutations, and return.

For each number in nums:

If the number is not in used, add it to used and append it to comb.
Recurse with the updated comb and used.
After recursion, remove the number from both comb and used.

Return permutations.

Complexity

Time Complexity: O(N * N!). There are N! permutations, and copying each permutation takes O(N). Space Complexity: O(N) for the recursion stack and the used set, excluding the output.