46. Permutations
Medium LeetCodeGiven an array nums
of distinct integers, return all the 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 the integers of
nums
are unique.
How to solve the problem
- Backtracking (DFS)
python
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
results = []
current_perm = [0] * n # Stores the current permutation
used = [False] * n # Tracks whether nums[i] is already used in the current permutation
def dfs(depth: int) -> None:
if depth == n:
results.append(current_perm.copy()) # Add a complete permutation to results
return
for idx, is_used in enumerate(used):
if not is_used:
current_perm[depth] = nums[idx] # Choose an unused number for this position
used[idx] = True # Mark as used
dfs(depth + 1) # Recurse to fill the next position
used[idx] = False # Backtrack: mark as unused for other branches
# No need to undo current_perm[depth], will be overwritten in the next iteration
dfs(0)
return results
Complexity
- Time complexity: O(K*C(n, k))
- Space complexity: O(K*C(n, k))
Comments
No comments yet. Be the first to comment!