Description
Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: [1,2,2] Output: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]
描述
- 此题是78题的递进题.
- 此题求给定数组的所有可能的子集，与78题不同，此题给定的数据可能有重复.
- 我们首先对给定的数组排序，然后如果当前元素与前一个元素相同，我们跳过进行下一步.
- 基本思路同78题完全一致.
# -*- coding: utf-8 -*- # @Author: 何睿 # @Create Date: 2018-12-25 21:24:06 # @Last Modified by: 何睿 # @Last Modified time: 2018-12-25 21:41:42 import copy class Solution: def subsetsWithDup(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ res = [[]] nums = sorted(nums) self.recursion(res, [], nums, 0, len(nums)) return res def recursion(self, res, path, nums, start, end): if start == end: return for i in range(start, end): if i != start and nums[i] == nums[i-1]: continue else: path.append(nums[i]) res.append(copy.deepcopy(path)) self.recursion(res, path, nums, i+1, end) path.pop() if __name__ == "__main__": so = Solution() res = so.subsetsWithDup([1, 1, 6, 2]) print(res)
源代码文件在这里.
