LeetCode 90. Subsets II

简介: Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

v2-8d455f0f21c5e94faf01c52439b5b54d_1440w.jpg

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)


源代码文件在这里.


目录
相关文章
|
Python
[LeetCode] Subsets
Recursive (Backtracking) This is a typical problem that can be tackled by backtracking. Since backtracking has a more-or-less similar template, so I do not give explanations for this method.
763 0
|
1天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
2天前
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
【LeetCode刷题】前缀和解决问题:742.寻找数组的中心下标、238.除自身以外数组的乘积
|
2天前
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名
【LeetCode刷题】二分查找:寻找旋转排序数组中的最小值、点名