[Leetcode][Python]47: Permutations II
浏览数：39 /
时间：2015年06月08日
# -*- coding: utf8 -*-
‘‘‘
__author__ = ‘[email protected]‘
47: Permutations II
https://oj.leetcode.com/problems/permutations-ii/
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].
===Comments by Dabay===
先排序，然后DFS。
注意去重，如果进入了一次DFS，用pre记录上次用的数字。这个pre只在DFS中的for中有效，所以每次进入进入新的DFS的时候，重新设置为None.
‘‘‘
class Solution:
# @param num, a list of integer
# @return a list of lists of integers
def permuteUnique(self, num):
res = []
num.sort()
self.DFS(res, [], None, num)
return res
def DFS(self, res, l, pre, nums):
if len(nums) == 0:
res.append(list(l))
pre = None
for i in xrange(len(nums)):
if nums[i] == pre:
continue
l.append(nums[i])
self.DFS(res, l, nums[i], nums[:i] + nums[i+1:])
l.pop()
pre = nums[i]
def main():
sol = Solution()
nums = [1,1,2]
print sol.permuteUnique(nums)
if __name__ == "__main__":
import time
start = time.clock()
main()
print "%s sec" % (time.clock() - start)
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
