47. Permutation II Leetcode Python

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], and [2,1,1].

generally finding all permutation will take N! time based on T(n) = n*T(n-1)

this approach we can trim some of the cases, example: num[i] == num[i-1] but we have not yet visit num[i - 1]

so it would be a little less than n! but still np

def backtrack(num, res, val, visit):
        if len(val) == len(num) and :
            res.append(val)
        for i in range(len(num)):
        	if i > 0 and visit[i - 1] == False and num[i - 1] == num[i]:
        		continue
            if visit[i] == False:
                visit[i] = True
                backtrack(num, res, val+[num[i]], visit)
                visit[i] = False
def permuteUnique(num):
    visit = [False for i in range(len(num))]
    res = []
    val = []
    num.sort()
    backtrack(num, res, val, visit)
    return res
num = [1, 3, 1]
print permuteUnique(num)

47. Permutation II Leetcode Python

原文：http://blog.csdn.net/hyperbolechi/article/details/44664573