In the Leetcode Permutations II problem solution 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 in C Programming
int factorial(int n){
return (n==0) || (n==1) ? 1 : n* factorial(n-1);
}
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
int** permuteUnique(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
int tmp[21] = {0};
int* c = calloc(numsSize, sizeof(int));
// calculate the returnSize
for (int i = 0; i < numsSize; i++) {
tmp[nums[i] + 10]++;
}
*returnSize = 1;
// calculate how many non-unique numbers there are (used to calculate returnSize)
for (int i = 0; i < 20; i++) {
if (tmp[i] > 1) {
*returnSize*= factorial(tmp[i]);
}
}
*returnSize = factorial(numsSize)/ (*returnSize == 0 ? 1 : *returnSize);
// initialize return and columnSizes arrays
int** ret = (int**)malloc(sizeof(int *) * (*returnSize));
*returnColumnSizes = (int*)malloc(sizeof(int)*(*returnSize));
for (int i = 0; i < *returnSize; i++) {
ret[i] = calloc(numsSize, sizeof(int));
(*returnColumnSizes)[i] = numsSize;
}
// generate permutations based on a non-recursive variation of the Heap's algorithm.
// decrease and conquer method by generating all permutations that end with the last element,
// and then switching the first and last.
int i = 0;
int j;
int added = 0;
int dupe = 0;
// add initial permutation to the list
memcpy(ret[added++], nums, sizeof(int) * numsSize);
while (i < numsSize) {
if (c[i] < i) {
// swap elements nums(0,i) (first and last)
if (i % 2 == 0) {
j = nums[0];
nums[0] = nums[i];
nums[i] = j;
} else {
// swap elements nums(c[i], i)
j = nums[c[i]];
nums[c[i]] = nums[i];
nums[i] = j;
}
// add to return array if not a duplicate
dupe = 0;
for (int k = 0; k < added; k++) {
if (memcmp(nums, ret[k], sizeof(int) * numsSize) == 0) {
dupe = 1;
break;
}
}
if (dupe == 0) {
memcpy(ret[added++], nums, sizeof(int) * numsSize);
}
c[i] = c[i] + 1;
i = 0;
} else {
c[i] = 0;
i++;
}
}
return ret;
}Solution in C++ Programming
class Solution {
private:
vector<vector<int>> result;
public:
// Returns true if nums[curr] does not match with any of the characters after nums[start]
bool shouldSwap(vector<int> &nums, int start, int curr) {
for (int i = start; i < curr; i++)
if (nums[i] == nums[curr])
return 0;
return 1;
}
void helper(vector<int>& nums, int left) {
if (left == nums.size()) result.push_back(nums);
else {
for (int i = left; i < nums.size(); i++) { // hold each character stationary.
// Proceed further for nums[i] only if it doesn't match with any of the numbers after nums[left]
bool check = shouldSwap(nums, left, i);
if (check) {
swap(nums[i], nums[left]); // recurse
helper(nums, left + 1);
swap(nums[i], nums[left]); // recurse
}
}
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
helper(nums, 0); // call helper function to compute permutations.
return result;
}
};Solution in Java Programming
class Solution {
List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
return backTrack(nums, 0);
}
public List<List<Integer>> backTrack(int[] nums, int idx) {
if(idx == nums.length) {
List<Integer> tempList = new ArrayList<>();
for(int i = 0; i < nums.length; i++) tempList.add(nums[i]);
if(!result.contains(tempList)) result.add(tempList);
} else {
for(int start = idx; start < nums.length; start++) {
swap(nums, start, idx);
backTrack(nums, idx + 1);
swap(nums, start, idx);
}
}
return result;
}
public void swap(int[] nums, int idx, int start) {
int temp = nums[idx];
nums[idx] = nums[start];
nums[start] = temp;
}
}Solution in Python Programming
class Solution:
def permuteUnique(self, nums):
L = []
def p(i):
if i == len(nums):
L.append(nums[:])
for j in range(i, len(nums)):
nums[i], nums[j] = nums[j], nums[i]
p(i + 1)
nums[i], nums[j] = nums[j], nums[i]
p(0)
L = list(set(map(lambda x : tuple(x),L)))
return LSolution in C# Programming
public class Solution
{
public IList<IList<int>> PermuteUnique(int[] nums)
{
IList<IList<int>> solution = new List<IList<int>>();
int n = nums.Length;
Array.Sort(nums);
Helper(solution, new List<int>(), n, nums, new bool[n]);
return solution;
}
private void Helper(IList<IList<int>> solution, IList<int> currentPath, int n, int[] nums, bool[] visited)
{
if(currentPath.Count == n)
{
solution.Add(new List<int>(currentPath));
return;
}
for(int i = 0; i < n; i++)
{
if(!visited[i])
{
currentPath.Add(nums[i]);
visited[i] = true;
Helper(solution, currentPath, n, nums, visited);
currentPath.RemoveAt(currentPath.Count - 1);
visited[i] = false;
while(i < n - 1 && nums[i] == nums[i + 1])
{
i++;
}
}
}
}
}Also read,