Question: https://oj.leetcode.com/problems/permutations-ii/
Question Name: Permutations II
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | class Solution: # @param num, a list of integer # @return a list of lists of integers def permuteUnique(self, num): stack = [] # The temporary lists for result used = [] # For stack[i], used[i] means the used # items' position in "num" appeared = set() # The appeared combination result = [] # Final result permutations fullFlag = (1 << len(num)) - 1 # The value of used[i], when # stack[i] is a full permutation # Initialize the stack and used, with a single integer in "num" for index in xrange(len(num)): if not (num[index],) in appeared: # Never appeared stack.append((num[index],)) used.append(1<<index) appeared.add((num[index],)) while len(stack) != 0: temp = stack.pop() usedState = used.pop() if usedState == fullFlag: # This is a final permutation result.append(list(temp)) else: # Try to append one unused integer for index in xrange(len(num)): # This integer is not used if usedState & (1<<index) == 0: nextState = temp + (num[index],) # This combination does not appear in previous rounds if not nextState in appeared: stack.append(nextState) used.append(usedState | (1<<index)) appeared.add(nextState) return result |
Take advantage of next permutation