algoadvance

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

Example:

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

Clarifying Questions

  1. Q: Can the input array nums contain any duplicate numbers? A: No, the problem specifies that the numbers in nums are distinct.

  2. Q: Can the input array nums be empty? A: Technically, yes, but since the problem specifies that we will receive an array of distinct integers, we will assume it is at least of length 1 for practical purposes.

Strategy

To solve this problem, we can use a backtracking approach which generates all possible permutations by exploring all candidate numbers for each position.

Here’s a step-by-step breakdown:

  1. Initialization: Start by initializing an empty list to store the results.
  2. Backtracking function: Define a function that will take the current permutation and the remaining numbers.
  3. Base Case: If there are no more numbers to add, append the current permutation to the result list.
  4. Recursive Step: For each of the remaining numbers, add it to the current permutation, then recursively call the function with the updated current permutation and the remaining numbers excluding the selected one.
  5. Return the Results: Finally, return the list of all collected permutations.

Code

from typing import List

def permute(nums: List[int]) -> List[List[int]]:
    res = []
    
    def backtrack(path, remaining):
        if not remaining:
            res.append(path)
            return
        
        for i in range(len(remaining)):
            backtrack(path + [remaining[i]], remaining[:i] + remaining[i+1:])
    
    backtrack([], nums)
    return res

# Example usage:
nums = [1, 2, 3]
print(permute(nums))

Time Complexity

The time complexity of this solution is (O(n \times n!)), where (n) is the length of the input list nums. This is because there are (n!) permutations and generating each permutation of length (n) takes (O(n)) time.

Try our interview co-pilot at AlgoAdvance.com