We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Permutations

Number: 46

Difficulty: Medium

Paid? No

Companies: Google, Amazon, Bloomberg, Microsoft, Meta, Apple, Uber, Booking.com, TikTok, Qualcomm, American Express, LinkedIn, Oracle, Adobe, Citadel, Goldman Sachs, Salesforce, Yahoo, eBay, ServiceNow, Zoho

Problem Description

(A short summary or question text)

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

Key Insights

  • Use backtracking to generate all possible permutations.
  • Build each permutation by selecting numbers one at a time.
  • When the current permutation reaches the length of nums, add it to the result.
  • Backtracking allows you to undo choices and explore different orderings.

Space and Time Complexity

Time Complexity: O(n * n!) - There are n! permutations, and constructing each permutation takes O(n) time. Space Complexity: O(n) - Recursion depth is limited to n, plus additional space for the current permutation.

Solution

The solution employs a backtracking algorithm. A helper function is used to build permutations recursively. At each step, the algorithm iterates through the available numbers, adds one to the current permutation if it has not been used yet, and recurses to handle the remaining numbers. Once the current permutation matches the length of the input array, it is added to the result list. Then, by "backtracking" (removing the last number added), the algorithm explores alternative possibilities. This systematic exploration ensures that all possible permutations are generated.

Code Solutions

def permute(nums):
    result = []
    
    def backtrack(current, remaining):
        # If no remaining elements, current permutation is complete.
        if not remaining:
            result.append(current.copy())
            return
        # Explore each candidate number.
        for i in range(len(remaining)):
            # Add the chosen number to the current permutation.
            current.append(remaining[i])
            # Recursively generate permutations with the remaining numbers.
            backtrack(current, remaining[:i] + remaining[i+1:])
            # Backtrack by removing the chosen number.
            current.pop()
    
    backtrack([], nums)
    return result

# Example usage:
print(permute([1,2,3]))
← Back to All Questions