Description

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

1
2
3
4
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]]
1
2
3
4
Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]
1
2
3
4
Example 3:

Input: nums = [1]
Output: [[1]]
1
2
3
4
Constraints:

1 <= nums.length <= 6
-10 <= nums[i] <= 10

All the integers of nums are unique.

Approach

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def permute(nums):
    res = []
    backtrack(nums, [], res)
    return res

def backtrack(nums, path, res):
    if not nums:
        res.append(path)
        return

    for i in range(len(nums)):
        backtrack(nums[:i] + nums[i+1:], path + [nums[i]], res)

# Example usage:
nums = [1, 2, 3]
print(permute(nums))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res=[]

        def dfs(index,ds):
            if index == len(nums):
                res.append(ds[:])
            for num in nums:
                if num not in ds:
                    ds.append(num)
                    dfs(index+1,ds)
                    ds.pop()
                    
        dfs(0,[])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:

    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []

        def backtrack(start):
            if start == len(nums):
                res.append(nums[:])
                return
            
            for i in range(start, len(nums)):
                if start != i:
                    nums[start], nums[i] = nums[i], nums[start]
                
                backtrack(start+1)

                if start !=i:
                    nums[start], nums[i] = nums[i], nums[start]

        backtrack(0)
        return res

# Example usage:
nums = [1, 2, 3]
solution = Solution()
print(solution.permute(nums))