LeetCode #46 #47 2018-07-30

46. Permutations

https://leetcode.com/problems/permutations/description/

方法还是套用模板，使用一个循环递归处理子问题。区别是这里并不是一直往后推进的，前面的数有可能放到后面，所以我们需要维护一个used数组来表示该元素是否已经在当前结果中，时间复杂度还是的指数量级。
注意在实现中有一个细节，就是在递归函数的前面，我们分别设置了used[i]的标记，表明改元素被使用，并且把元素加入到当前结果中，而在递归函数之后，我们把该元素从结果中移除，并把标记置为false，这个我们可以称为“保护现场”，递归函数必须保证在进入和离开函数的时候，变量的状态是一样的，这样才能保证正确性。这种方法在很多题目（几乎所有NP问题）中一直用到。
递归代码如下：

class Solution:
    # Solution1 - DFS recursively 
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []
        if not nums or len(nums) == 0:
            return result
        used = [False] * len(nums)
        self.helper(nums, used, [], result)
        return result
    
    def helper(self, nums, used, path, result):
        if len(path) == len(nums):
            result.append(list(path))
            return
        for i in range(len(nums)):
            if not used[i]:
                used[i] = True
                path.append(nums[i])
                self.helper(nums, used, path, result)
                path.pop()
                used[i] = False

迭代一般就是要清楚每次加入一个新的元素，我们应该做什么，这里其实还是比较清晰的，假设有了前i个元素的所有permutation，当第i + 1个元素加进来时，我们要做的就是将这个元素带入每一个之前的结果，并且放到每一个结果的各个位置中。因为之前的结果没有重复，所以带入新元素之后也不会有重复（当然这里假设数字集合本身是没有重复的元素的）。上面的代码有时候乍一看可能觉得只有两层循环，但因为注意第二层循环是对于res进行遍历的，而res是一直在以平方量级增长的，所以总的时间复杂度还是指数量级以上的。
迭代代码如下：

class Solution:
    # Solution 2 - Iteration
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = [[]]
        for num in nums:
            cur_res = []
            for res in result:
                for i in range(len(res) + 1):
                    res.insert(i, num)
                    cur_res.append(list(res))
                    res.remove(res[i])
            result = cur_res
        return result

47. Permutations II

https://leetcode.com/problems/permutations-ii/description/

这个题跟Permutations非常类似，唯一的区别就是在这个题目中元素集合可以出现重复。那么如何避免这种重复呢？方法就是对于重复的元素循环时跳过递归函数的调用，只对第一个未被使用的进行递归，那么这一次结果会出现在第一个的递归函数结果中，而后面重复的会被略过。如果第一个重复元素前面的元素还没在当前结果中，那么我们不需要进行递归。
递归代码如下：

class Solution:
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []
        if not nums or len(nums) == 0:
            return result
        nums.sort()
        self.helper(nums, [False] * len(nums), [], result)
        return result
    
    def helper(self, nums, used, path, result):
        if len(path) == len(nums):
            result.append(list(path))
            return
        for i in range(len(nums)):
            if i > 0 and nums[i-1] == nums[i] and used[i-1]:
                continue
            if not used[i]:
                used[i] = not used[i]
                path.append(nums[i])
                self.helper(nums, used, path, result)
                path.pop()
                used[i] = not used[i]

做题时的感悟:

1. 这种避免重复的机制有点难理解，下面给出一种合理的解释：
   假设有两个1，排序后位置不同，我们规定这两个1在排序中出现的顺序必须和数组中位置顺序一样，也就是第一个1只能出现在前面，第二个1只能出现在后面，这样就消除了重复解。对应到代码中，要排除的情况就是在前面的位置选择第二个1，这时检查发现第一个1还没用过就是这种情况，于是可以直接跳过了。
2. 对于这种有重复元素的题，处理重复元素的必要条件是数组中元素有序，所以先对数组进行排序的必须的。