Teaching Kids Programming – Recursive Permutation Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

Full Permutation Algorithm in Recursion

For each possible permutation, we can swap current character with every character right to it. Then we recursively permutate the next character. After swapping and recursive call to next character, we need to swap the character back (restore current stats)

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def dfs(left, ans):
            if left == len(nums):
                ans.append(deepcopy(nums))
                return
            for i in range(left, len(nums)):
                nums[i], nums[left] = nums[left], nums[i]
                dfs(left + 1, ans)
                nums[i], nums[left] = nums[left], nums[i]
        ans = []
        dfs(0, ans)
        return ans

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def dfs(left, ans):
            if left == len(nums):
                ans.append(deepcopy(nums))
                return
            for i in range(left, len(nums)):
                nums[i], nums[left] = nums[left], nums[i]
                dfs(left + 1, ans)
                nums[i], nums[left] = nums[left], nums[i]
        ans = []
        dfs(0, ans)
        return ans

The array in Python is by reference, so that when we reach the end, we need to make a deep copy of the current solution. The time complexity is O(N!) as there are N! full permutations, and so is the space complexity.

Python Permutation Function

Using the permutations from itertools, we can do this one-liner using the existing library.

1
2
3

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        return list(itertools.permutations(nums)) 

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        return list(itertools.permutations(nums)) 

See also: The Permutation Iterator in Python

Permutations and Combinations

• Using Bitmasking Algorithm to Compute the Combinations of an Array
• Teaching Kids Programming – Recursive Backtracking Algorithm to Compute the Combinations
• Teaching Kids Programming – Recursive Permutation Algorithm
• Teaching Kids Programming – Introduction to Permutation and Combination
• Teaching Kids Programming – Three Algorithms to Compute the Combination Number
• A Recursive Full Permutation Algorithm in Python
• The Permutation Iterator in Python
• GoLang: Full Permutation Command Line Tool
• The Permutation Algorithm for Arrays using Recursion
• Full Permutation Algorithm Implementation in BASH

–EOF (The Ultimate Computing & Technology Blog) —