2025-09-15 19:40

Status: adult

Tags: leetcode leetcode-medium backtrack Backtracking Intro Subsets

Permutations

Code

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        
        res, sol = [], []
        n = len(nums)
 
        def backtrack():
            # base case
            if len(sol) == n:
                res.append(sol[:])
                return
 
            for num in nums:
                if num not in sol:
                    sol.append(num)
                    backtrack()
                    sol.pop()
 
        backtrack()
        return res

Explanation

1. similar to the Subsets problem except backtrack doesn’t take any parameters

Base Case(s): when length of sol = length of nums Choices: all permutations of the elements in nums Constraints: each element can only be used once in a permutation Backtracking Step: Pop the last number added

References

Greg Hogg