LeetCode 46. Permutations

October 03, 2020

We could use itertools.permutations, but that doesn't give us any interview practice!

We can solve this with a head-recursive function that returns the first element in the list plus every combo of following elements.

We'll still use itertools.permutations to write test cases.

The runtime of this algorithm is the same as the number of permutations, which is $O(n!)$ .

from itertools import permutations
from typing import List
import unittest

class Test(unittest.TestCase):

    def setUp(self):
        self.s = Solution()

    def getSoln(self, l):
        return [list(x) for x in permutations(l)]

    def test_examples(self):
        self.assertEqual(self.s.permute([1,2,3]), [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]])
        # Also verify my test-verifying method
        self.assertEqual(self.getSoln([1,2,3]), [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]])

    def test_empty(self):
        self.assertEqual(self.s.permute([]), [])

    def test_single(self):
        self.assertEqual(self.s.permute([-1]), self.getSoln([-1]))
        self.assertEqual(self.s.permute([0]), self.getSoln([0]))
        self.assertEqual(self.s.permute([1]), self.getSoln([1]))

    def test_long(self):
        self.assertEqual(self.s.permute([23,45,1,-34,7,81,3]), self.getSoln([23,45,1,-34,7,81,3]))

class Solution:

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

if __name__ == "__main__":
    unittest.main()