LeetCode #78 #90 2018-07-30

78. Subsets

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

子集问题是经典的NP问题，复杂度上我们就无法强求了，肯定是非多项式量级的。一般来说这个问题有两种解法：递归和迭代。
递归解法直接使用模板即可。
迭代解法主要需要理解，在原有集合加入一个新的数字，如何得到包含新数字的所有子集。其实就是在原有的集合中对每集合中的每个元素都加入新元素得到子集，然后放入原有集合中（原来的集合中的元素不用删除，因为他们也是合法子集）。时间和空间都是取决于结果的数量，也就是O(2ⁿ)。
位运算解法。对于这道题，因为集合中没有重复的数字，所以不用考虑结果重复的问题，可以使用位运算这一巧妙的方法来解，思路清晰，代码简洁，但不是通法。
递归代码如下：

class Solution:
    # Solution1 - DFS recursively 
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []
        self.helper(nums, 0, [], result)
        return result
        
    def helper(self, nums, index, path, result):
        result.append(list(path))
        for i in range(index, len(nums)):
            self.helper(nums, i + 1, path + [nums[i]], result)

迭代代码如下：

class Solution:
    # Solution2 - Iteratively 
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = [[]]
        for num in nums:
            result += [item + [num] for item in result]
        return result

位运算代码如下：

class Solution:
    # Solution3 - Bit Manipulation
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []
        for i in range(1 << len(nums)):
            temp = []
            for j in range(len(nums)):
                if i >> j & 1:
                    temp.append(nums[j])
            result.append(temp)
        return result    

90. Subsets II

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

这个问题同样有两种解法：递归和迭代。
递归解法，主要注意跟上一道题的区别，就是对重复结果的排除。我们只关心取多少个x元素，不关心取哪几个。所以规定当前循环必须从第一个x开始连续取，不可以跳过第一个x直接取第二个x，这样会导致重复结果。
迭代解法，为了避免重复，每当遇到重复元素的时候我们就只把当前结果集的后半部分加上当前元素加入到结果集中，因为后半部分就是上一步中加入这个元素的所有子集，上一步这个元素已经加入过了，前半部分如果再加就会出现重复。
递归代码如下：

class Solution:
    # Solution1 - DFS recursively 
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []
        nums.sort()
        self.helper(nums, 0, [], result)
        return result
    
    def helper(self, nums, index, path, result):
        result.append(list(path))
        for i in range(index, len(nums)):
            if i > index and nums[i] == nums[i - 1]:
                continue
            self.helper(nums, i + 1, path + [nums[i]], result)

迭代代码如下：

class Solution:
    # Solution2 - Iteratively
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = [[]]
        if not nums or len(nums) == 0:
            return result
        nums.sort()
        for i in range(len(nums)):
            if i == 0 or nums[i] != nums[i - 1]:
                last_len = len(result)
            for j in range(len(result)-last_len, len(result)):
                result.append(result[j] + [nums[i]])
        return result