Question: https://oj.leetcode.com/problems/permutations/
Question Name: Permutations
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 | class Solution: # @param num, a list of integer # @return a list of lists of integers def permute(self, num): stack = [] # The temporary lists for result used = [] # For stack[i], used[i] means the used # items' position in "num" 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)): stack.append([num[index]]) used.append(1<<index) while len(stack) != 0: temp = stack.pop() usedState = used.pop() if usedState == fullFlag: # This is a final permutation result.append(temp) else: # Try to append one unused integer for index in xrange(len(num)): # This integer is not used if usedState & (1<<index) == 0: stack.append(temp + [num[index]]) used.append(usedState | (1<<index)) return result |
Can’t figure out iteration version…
The usage of stack is kind of simulating stack.