Skip to content

46. Permutations

Problem

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|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|0,1],[1,0]]

Example 3:

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

Constraints:

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

Solve

DFS or BFS

O(n!)

Goes through each stage of the permutations until we using all available number in nums array

from typing import List


class Solution:
    def dfs(self, lastArray, adjNode):
        result = []

        if len(adjNode) == 0:
            result = lastArray
            return [result]

        for node in adjNode:
            newArray = lastArray + [node]
            newAdjNode = adjNode - set([node])
            result = result + self.dfs(newArray, newAdjNode)
        return result

    def permute(self, nums: List[int]) -> List[List[int]]:
        return self.dfs([], set(nums))

To test above code:

def test():
    a = Solution()
    # Example 1:
    nums = [1,2,3]
    result = [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1|1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

    print("Test 1 is", result == a.permute(nums))
    # Example 2:
    nums = [0,1]
    result = [[0,1],[1,0|0,1],[1,0]]

    print("Test 2 is", result == a.permute(nums))
    # Example 3:
    nums = [1]
    result = [[1|1]]

    print("Test 3 is", result == a.permute(nums))

if __name__ == "__main__":
    test()

Reuse global variable

O(n!)

Taking approach from 77. Combinations, we can try reuse some of our created array to make the code run faster, while minimize total for loop

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        path = []
        def helper(words):
            if len(words) == 1:
                return [path+list(words)]
            result = []
            t = words.copy()
            for i in words:
                path.append(i)
                t.remove(i)
                result += helper(t)
                t.add(i)
                path.pop()
            return result

        return helper(set(nums))
Last update : September 17, 2023
Created : August 16, 2023