Question:

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

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

Constraints:

1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique.

Solution:

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

Algorithm

The problem can be solved by recursively generating all permutations of the array. For a given array nums, the algorithm works as follows:

If the length of nums is 1, return a list containing nums.
For each element in nums, generate all permutations of the remaining elements using recursion. This can be done by creating a new array without the current element, and calling the permutation function recursively with the new array.
For each permutation generated in step 2, add the current element to the beginning of the permutation.
Return the list of all permutations generated in step 3.

Java Implementation

Here’s the Java implementation of the algorithm:

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        permute(nums, new boolean[nums.length], new ArrayList<>(), res);
        return res;
    }
    
    private void permute(int[] nums, boolean[] used, List<Integer> cur, List<List<Integer>> res) {
        if (cur.size() == nums.length) {
            res.add(new ArrayList<>(cur));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                cur.add(nums[i]);
                used[i] = true;
                permute(nums, used, cur, res);
                cur.remove(cur.size() - 1);
                used[i] = false;
            }
        }
    }
}

The permute() function takes an array nums, and returns a list of all permutations of its elements. The function uses a helper function permute() to generate the permutations recursively. The permute() function takes the following arguments:

nums: the array of integers to be permuted
used: a boolean array indicating which elements of nums have already been used in the current permutation
cur: a list representing the current permutation being generated
res: the list of all permutations generated so far

Python Implementation

Here’s the Python implementation of the algorithm:

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if len(nums) == 1:
            return [nums]
        res = []
        for i in range(len(nums)):
            sub_res = self.permute(nums[:i] + nums[i+1:])
            for j in sub_res:
                res.append([nums[i]] + j)
        return res

The permute() function takes an array nums, and returns a list of all permutations of its elements. The function uses recursion to generate the permutations. The permute() function takes the following arguments:

nums: the array of integers to be permuted

Time Complexity

The time complexity of the algorithm is O(n!), where n is the length of the input array. This is because there are n! permutations of n distinct elements, and the algorithm generates each permutation once.

Space Complexity

The space complexity of the algorithm is O(n^2), where n is the length of the input array. This is because the algorithm generates n! permutations, each of which has length n. The algorithm uses additional space to store the list of permutations generated so far.