[LeetCode] 046. Permutations
-
date_range April 04, 2019 - Thursday info
Problem (Medium)
Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3] Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
Approach 1: (My Solution) Depth First Searching (Backtracking)
Idea
Similar idea with Problem 038 using backtracking (recursive)
Solution
class Solution1:
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
res = []
self.dfs(nums, [], res)
#return set([tuple(i) for i in res])
return res
def dfs(self, nums, item, res):
if len(item) == len(nums):
res.append(item)
return
for i in range(len(nums)):
if nums[i] in item:
continue
self.dfs(nums, item + [nums[i]], res)
Complexity
- Time: $O()$?
- Space: $O()$?
KF