# The solution is accepted but I'm not sure in it's complexity

• I've used slightly modified code for Permutations task with the following additions:
Suppose that we have the following array

[0_a;0_b;1;1]
for correct solution we must ensure that items of the same value shouldn't switch places in permutation.
Basically it means that any of the following is valid

0_a; 1; 0_b; 1
1;0_a;0_b;1
etc
but this not
0_b;0_a;1;1

for enforcing that rule I'm doing simple cycle that checks the following condition:
If in left part of array there is element with the same value that isn't used in permutation, it means that we trying to broke invariant. Skip this permutation path.
The code is simple (~75% is reused from basic permutation task), but I still not sure that this is the best way to solve that task.

``````public class Permutations2 {
private boolean[] marked;
private int[] num;
private Integer[] currentPermutation;

List<List<Integer>> result = new ArrayList<>();

public List<List<Integer>> permuteUnique(int[] num) {
marked = new boolean[num.length];
currentPermutation = new Integer[num.length];
this.num = num;

Arrays.sort(num);
permute(0);

return new ArrayList<>(result);
}

private void permute(int currentIndex) {
if(currentIndex==num.length) {
return;
}

for (int i = 0; i < num.length; i++) {

// If in left there is an element with the same value but not used in permutation
// it means that we have case when we 1(at0) 1(at1) try to put 1(at1) before 1(0), and
// it will generate duplicates.
// so there is simple check for that case by iterating
if(!marked[i]) {
boolean hasLessNotMarked = false;
int j = i-1;
while (j>=0 && num[i]==num[j]) {
if(!marked[j]) {
hasLessNotMarked = true;
}
j--;
}

if(!hasLessNotMarked) {
marked[i] = true;
currentPermutation[currentIndex] = num[i];
permute(currentIndex + 1);
marked[i] = false;
}
}
}
}
}``````

• A python solution using the idea of next_permutation. Note that in this case since we may have duplicates, we use >= to judge the next permutation rather than > as we did in Permutation I:

``````class Solution:
# @param num, a list of integer
# @return a list of lists of integers
def permuteUnique(self, num):
n = len(num)
if n == 0: return []
num.sort()
allists = []
while True:
allists.append(num[:])
p = n-1
while p > 0 and num[p-1] >= num[p]:
p -= 1
if p == 0: break
q = p
while q < n and num[q] > num[p-1]:
q += 1
# swap
num[p-1], num[q-1] = num[q-1], num[p-1]
num[p:] = num[p:][::-1]
return allists
``````

The complexity of this algorithm is the number of valid unique permutations. Mathematically speaking, suppose we have N elements in the array, with M unique values, hence M <= N. Let D(m) denote the number of duplicates of element m, m = 1, 2, ... M, then the complexity of my algorithm above is:

N! / (D(1) ! x D(2) ! x D(3)! x ... x D(m)!)

In the case of no duplicate, i.e., M = N and D(m) = 1 for all m, this algorithm simply reduces to the normal permutation generating algorithm.

Hope this helps.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.