Permutations II
Given a collection of numbers, nums
, that might contain duplicates, return all possible unique permutations in any order.
Example 1:
Input: nums = [1,1,2]
Output:
[[1,1,2], [1,2,1], [2,1,1]]
Example 2:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Constraints:
1 <= nums.length <= 8
-10 <= nums[i] <= 10
Solution
Let's fill in the logic for backtracking1:
path_length
: indicates the number of elements inpath
used
: an array storing the status of whether an element is used.is_leaf
:path_length == len(nums)
, whenpath_length
is the same asnums
's length.get_edges
andis_valid
: all elements that are unused (used[i]==Flase
).
In the implementation, we use an array used
to store the whether an element has been used or not.
Everytime we use a number, we add it into the path
and we mark it used
(used[idx] = True
).
Since there are duplicate values, let's apply methods in Deduplication to deduplicate the results.
we want to sort the nums
array so that duplicate elements are consecutive, and only proceed when the current element is the first of its occurrance.
Implementation
1def permuteUnique(self, nums: List[int]) -> List[List[int]]:
2 used = [False] * len(nums)
3 ans = []
4 nums.sort()
5
6 def dfs(path_length, path):
7 if path_length == len(nums):
8 ans.append(path[:])
9 return
10
11 for i in range(0, len(nums)):
12 if used[i]: continue
13 if(i > 0 and nums[i] == nums[i-1] and not used[i-1]): continue
14 path.append(nums[i])
15 used[i] = True
16 dfs(path_length + 1, path)
17 used[i] = False
18 path.pop()
19
20 dfs(0, [])
21 return ans
Which data structure is used to implement priority queue?
Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.
Which of the following method should we use to solve this problem?
Solution Implementation
What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.