ゼロから始めるLeetCode Day96 「78. Subsets」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day95「82. Remove Duplicates from Sorted List II」

Twitterやってます。

技術ブログ始めました！！
技術はLeetCode、Django、Nuxt、あたりについて書くと思います。こちらの方が更新は早いので、よければブクマよろしくお願いいたします！

お知らせ

Day 100でQiitaでの投稿はひとまず区切りを付けようかと思います。
タグの記事が僕の記事ばかりになってしまうのもいかがなものかと思いましたし、他に有益な情報を提供している方の邪魔になってしまうこともあると考えたので、こうすることにしました。
至らない部分は多々ありましたが、今までお付き合い頂きありがとうございました。

問題を解いて記事を書く、というのは上記の個人ブログで続けるつもりですし、興味ある方はたまにそちらを覗いていただけると嬉しいです。
Twitterの方のアカウントはほとんど更新通知用と化しているので、Leetcodeを解く記事について気になる方はそちらも合わせてフォローいただくと良いかもしれません。

問題

78. Subsets
難易度はMedium。
コーディング面接対策のために解きたいLeetCode 60問からの抜粋です。

問題としては、異なる整数の集合numsが与えられます。
その中の可能なすべての部分集合を返します。
なお、解の集合には重複した部分集合を含んではいけません。

Example:

Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

解法

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        def dfs(temp,end):
            ans.append(temp+[])
            if len(nums) == len(temp):
                return
            for i in nums:
                if i > end:
                    temp.append(i)
                    dfs(temp,i)
                    temp.pop()
        dfs([],float(-inf))
        return ans
# Runtime: 32 ms, faster than 86.56% of Python3 online submissions for Subsets.
# Memory Usage: 13.8 MB, less than 90.09% of Python3 online submissions for Subsets.

dfsを実装して解くという方法を取りました。
再帰で解くか迷いましたが個人的にこちらの方が書きやすそうだったのでこちらの方法で書きました。

集合、と効くと前々回のsetなども考えられると思いましたが、こうした全てを列挙する場合はこちらの方が読みやすいかと思います。

比較的目新しいこともないのでこの辺りにしておこうかと思います。
では今回はここまで。お疲れ様でした。