leetcode-46 Permutations

# Given an array nums of distinct integers, return all 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 integers in nums are unique.

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []

        def backtrack(current_perm, remaining):
            # Base case: no more elements to add
            if not remaining:
                result.append(current_perm[:])  # Make a copy!
                return

            # Try each remaining element
            for i in range(len(remaining)):
                # Choose
                current_perm.append(remaining[i])

                # Explore: recurse with remaining elements
                backtrack(current_perm, remaining[:i] + remaining[i+1:])

                # Unchoose (backtrack)
                current_perm.pop()

        backtrack([], nums)
        return result

    # Alternative: Using set for tracking used elements
    def permute2(self, nums: List[int]) -> List[List[int]]:
        result = []
        n = len(nums)

        def backtrack(current_perm):
            if len(current_perm) == n:
                result.append(current_perm[:])
                return

            for num in nums:
                if num not in current_perm:
                    current_perm.append(num)
                    backtrack(current_perm)
                    current_perm.pop()  # backtrack

        backtrack([])
        return result

# Time Complexity: O(n! * n) - n! permutations, O(n) to build each
# Space Complexity: O(n) - recursion depth
#
# Backtracking Template:
# 1. Choose: Add element to current path
# 2. Explore: Recurse with updated state
# 3. Unchoose: Remove element (backtrack)