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]:continueif visit[i] == False:visit[i] = Truebacktrack(num, res, val+[num[i]], visit)visit[i] = Falsedef permuteUnique(num):visit = [False for i in range(len(num))]res = []val = []num.sort()backtrack(num, res, val, visit)return resnum = [1, 3, 1]print permuteUnique(num)
，一个积极奋进的目标，一种矢志不渝的追求。
