DEV Community

loading...

Leetcode Permutations Problem: Python Solution

Justin Bermudez
・1 min read

Given a collection of distinct integer, return all possible permutations.

Example:
Input: [1, 2, 3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

Leetcode problem can be found here

We need to understand what a permutation is; a way in which a set of things can be ordered. So our given input of numbers, we must find every possible combination starting with first number, then second number, then so on.

The way I approached this problem was by finding out how I wanted to initially loop through the whole input array.

We want to keep track of our result we want to output at all times and we want to constantly append this with

for i in range(len(array)):
    newArray = array[:i] + array[i+1:]
    newCurrentArray = currentArray + [array[i]]
Enter fullscreen mode Exit fullscreen mode

this is our main algorithm that will constantly look for the different permutations. We now have to call this recursively
to get every permutation

def getPermutations(array):
    result = []
    helper(array, [], result)
    return result
def helper(array, current, permutations):
    if not len(array) and len(current):
        oermutations.append(current)
    else:
        for i in range(len(array)):
            newArr = array[:i] + array[i+1:]
            newCurr = current + [array[i]]
            helper(newArr, newCurr, permutations)
Enter fullscreen mode Exit fullscreen mode

Discussion (0)