Permutations.py

# Question link - https://leetcode.com/problems/permutations/description/?envType=study-plan-v2&envId=top-interview-150

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        # Sol3: With backtracking approch 
        res = []
        # basecase 
        if len(nums) == 1:
            return [nums[:]]

        # Go through the decision tree
        for i in range(len(nums)):
            n = nums.pop(0)
            perms = self.permute(nums)

            for perm in perms:
                perm.append(n)
            res.extend(perms)
            nums.append(n)

        return res

        # # Sol2: Without using the recursive approch 
        # # Same complexities 
        # perms = [[]] 
        # for n in nums:
        #     new_perms = [] 
        #     for p in perms:
        #         for i in range(len(p) + 1):
        #             p_copy = p.copy()
        #             p_copy.insert(i,n)
        #             new_perms.append(p_copy)
        #     perms = new_perms
        # return perms

        # # Sol1 : O(n! * n^2) , O(n! * n^2)
        # # Recursive - subproblem concepts
        # # Base case 
        # if len(nums) == 0:
        #     return [[]]

        # # Start perms with except one elements
        # perms = self.permute(nums[1:])
        # res = [] 

        # # Go through each perms
        # for p in perms:
        #     for i in range(len(p) + 1):
        #         p_copy = p.copy()
        #         p_copy.insert(i , nums[0])
        #         res.append(p_copy)

        # return res