Permutations II – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
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
C++ Permutations II LeetCode Solution
class Solution {
public:
void recursion(vector<int> num, int i, int j, vector<vector<int> > &res) {
if (i == j-1) {
res.push_back(num);
return;
}
for (int k = i; k < j; k++) {
if (i != k && num[i] == num[k]) continue;
swap(num[i], num[k]);
recursion(num, i+1, j, res);
}
}
vector<vector<int> > permuteUnique(vector<int> &num) {
sort(num.begin(), num.end());
vector<vector<int> >res;
recursion(num, 0, num.size(), res);
return res;
}
};
Java Permutations II LeetCode Solution
public class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if(nums==null || nums.length==0) return res;
boolean[] used = new boolean[nums.length];
List<Integer> list = new ArrayList<Integer>();
Arrays.sort(nums);
dfs(nums, used, list, res);
return res;
}
public void dfs(int[] nums, boolean[] used, List<Integer> list, List<List<Integer>> res){
if(list.size()==nums.length){
res.add(new ArrayList<Integer>(list));
return;
}
for(int i=0;i<nums.length;i++){
if(used[i]) continue;
if(i>0 &&nums[i-1]==nums[i] && !used[i-1]) continue;
used[i]=true;
list.add(nums[i]);
dfs(nums,used,list,res);
used[i]=false;
list.remove(list.size()-1);
}
}
}
Python 3 Permutations II LeetCode Solution
def permuteUnique(self, nums):
res = []
nums.sort()
self.dfs(nums, [], res)
return res
def dfs(self, nums, path, res):
if not nums:
res.append(path)
for i in xrange(len(nums)):
if i > 0 and nums[i] == nums[i-1]:
continue
self.dfs(nums[:i]+nums[i+1:], path+[nums[i]], res)
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1
Leave a comment below
