047.permutationsII.md

47. Permutations II

Questions:

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

Analysis:

• 第一种：
  • 第一步，生成[1]，
  • 第二步，把2，插入上一步的[1]的所有可能位置中，得到[2,1],[1,2]，
  • 第三步，把3，插入上一步的结果中。对于[2,1]，3能插入的所有可能位置是3个，得到[3,2,1], [2,3,1],[2,1,3]。对于[1,2]，3能插入的所有可能位置是3个，得到[3,1,2], [1,3,2], [1,2,3]。
  • 如果输入数组有N个，就将上面的迭代进行N次。
  • 上面的代码可以用递归或者迭代来实现
  • 递归和迭代的区别
  • 递归是函数里面调用自己的本身
  • 迭代就是A不停调用B，顺序循环。 *第二种：交换法SWAP方法

Solution1: Iterative迭代

Time Complexity - O(n!)， Space Complexity - O(n)。

class Solution(object):
    def permuteUnique(self, nums):
        ans = [[]]
        for n in nums:  #有n个，可以插入
            new_ans = []  
            for l in ans:
                for i in xrange(len(l)+1): #插入l+1个位置
                    new_ans.append(l[:i]+[n]+l[i:])
                    if i<len(l) and l[i]==n: break    #handles duplication
            ans = new_ans
        return ans

Solution2: Recursive递归

class Solution(object):
	def permuteUnique(self, nums):
	    if not nums:
	        return []
	    nums = sorted(nums)
	    res = []
	    path = []        
	    self.dfs(nums, path, res)
	    return res
	    
	def dfs(self, s, path, res):
	    if not s:
	        res.append(path)
	        return
	    
	    for i in xrange(len(s)):
	        if i>0 and s[i]==s[i-1]:
	            continue
	        self.dfs(s[:i]+s[i+1:], path+[s[i]], res)

Solution3: Very short python:

def permuteUnique(self, nums):
    perms = [[]]
    for n in nums:
        perms = [p[:i] + [n] + p[i:]
                 for p in perms
                 for i in xrange((p + [n]).index(n) + 1)]
    return perms

本题关键：

• 递归或者迭代方法；swap交换法[本题我没看]
• DFS是一种搜索算法，穷尽所有可能性。