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

概要

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

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

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

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

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

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

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

次回
ゼロから始めるLeetCode Day97 「349. Intersection of Two Arrays」

Twitterやってます。

問題

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なども考えられると思いましたが、こうした全てを列挙する場合はこちらの方が読みやすいかと思います。

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