LeetCode 双刀流: 90. Subsets II

90. Subsets II

今天挑选了「90. Subsets II」的题目,这是一道类似「排列组合」的练习题。排列组合的基本想法就是把所有的可能穷举出来,重点在於如何让这个过程穷举的过程更有效率。所以在本题里面我们试着用递回的概念来转化原本的问题,试着让过程可以被简化。

先看一下题目描述

Given an integer array nums that may contain duplicates, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order.

再搭配范例理解题目

  • Example 1:
Input: nums = [1,2,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]
  • Example 2:
Input: nums = [0]
Output: [[],[0]]

Subsets(子集合)是从原始资料中任意挑选部分的元素所形成的集合称之,这个题目要把所有的 Subsets 挑选出来。

开始实作

在理解完题目与条件之後,那我们下一步就开始「#初探直觉解」并且一起尝试「#刻意优化」的过程:

方法 ①:穷举法

第一种方法采用穷举法的方法用两个回圈把所有可能都跑过一次,只是在过程中会将「已经被考虑过元素组合剔除」。

用 Python 实作一次

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
	
        nums.sort()
        ans = [[]]
        
        for num in nums:
            for index in range(len(ans)):
                temp = ans[index] + [num]
                if temp not in ans:
                    ans.append(temp)
        
        return ans

也可以用 JavaScript 复刻一次

var subsetsWithDup = function(nums) {
    nums.sort((a,b)=>a-b);
    
    let ans = [[]]
    for (let num of nums){
        let l = ans.length;
        for (let j = 0; j < l; j++) {
            tmp = [...ans[j], num]
            if(!ans.includes(tmp))
                ans.push(tmp);
        }
    }
    return [...new Set(ans.map(JSON.stringify))].map(JSON.parse);
};

提得一提的是由於 JavaScript 会有 deep copy 的问题,所以这边用了一个比较 tricky 的方法来处理 not in 的判断。

方法 ②:递回法

任意挑选部分的元素」这个行为很像是排列组合(permutation)在做的事情,所以这里我们使用递回的方式来处理 permutation 议题,从一个元素开始,每一层多增加一个元素的方式直到全部考虑完毕。大致的概念如下图:

用 Python 实作一次

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        powerset = []
        
        def permute(arr, index):
            powerset.append(arr)
            for i in range(index, len(nums)):
                if i != index and nums[i] == nums[i-1]:
                    continue
                permute(arr+[nums[i]], i+1)

                         
        permute([], 0)
        return powerset

也可以用 JavaScript 复刻一次


var subsetsWithDup = function(nums) {
    nums.sort()
    const powerset = [];
    
    function permute(arr, index) {
        powerset.push(arr)     
        for(let i = index; i < nums.length; i++) {
            if(i !== index && nums[i] === nums[i-1])
                continue;
            permute([...arr, nums[i]], i+1)
        }
    }
    permute([], 0);
    return powerset;
};

反思沉淀

在这个题目中,我们试图将原始的排列问题转化成递回的概念来解。透过递回来记忆部分的资讯,再每一层展开时只需要计算那些真的需要被计算的部分,而不用真的穷举出所有的可能。这个搭配递回来简化穷举法的方法称为「回溯(Backtracking)」,核心概念就是在穷举的过程中尽可能的筛选掉不符合的组合。

举一反三看看相似题

最後可以从题目提供的相似题看一下有哪些类似的题目,适合作为你下一个尝试的练习:


嗨,大家好!我是维元,一名擅长网站开发与资料科学的双栖工程师,斜杠於程序社群【JSDC】核心成员及【资料科学家的工作日常】粉专经营。目前在 ALPHACamp 担任资料工程师,同时也在中华电信、工研院与多所学校等单位持续开课。拥有多次大型技术会议讲者与竞赛获奖经验,持续在不同的平台发表对 #资料科学、 #网页开发 或 #软件职涯 相关的分享,邀请你加入 订阅 接收最新资讯。


<<:  【Side Project】 订单清单 - 资料库新增状态栏位

>>:  day20 在ui蒐集flow,能取代liveData吗?

Day 4 Ruby 变数与资料型别 Variable and Data Type

写在前面 因为发现昨天在讲基础运算子的时候很多地方需要先知道变数跟资料型别,所以今天赶快来补充一下。...

[Day26]ISO 27001 附录 A.14 系统获取、开发及维护

A.14 系统获取、开发及维护 A.14.1 资讯系统之安全要求事项 目标:确保资讯安全系跨越整个生...

JAVA - JAVA Maven 错误处理

JAVA - JAVA Maven 错误处理 参考资料 参考资料1:命令行mvn打包的时候报错:No...

D03 - Hello Firmata

将 Arduino Uno 插上电脑後,如果顺利的话作业系统会自动安装「USB 转 COM 晶片」之...

Day 30 : 第一个 MQTT 智慧装置

MQTT 通讯协定 最後一天就是要把大家领进门, 来把上回的智慧装置串接到 Home Assista...