permute_unique.py

# Given a collection of numbers that might contain duplicates,
# return all possible unique permutations.

# For example,
# [1,1,2] have the following unique permutations:
# [
# [1,1,2],
# [1,2,1],
# [2,1,1]
# ]

def permute_unique(nums):
    perms = [[]]
    for n in nums:
        new_perms = []
        for l in perms:
            for i in range(len(l) + 1):
                new_perms.append(l[:i] + [n] + l[i:])
                if i < len(l) and l[i] == n:
                    break  # handles duplication
        perms = new_perms
    return perms