[leetcode] subset

subset

• 한 집합이 주어질때 모든 부분집합을 리턴

solution1

• itertools 의 combinations 이용
• 0 ~ len(nums) 크기의 조합 찾아서 결과값에 추가

code1

from itertools import combinations

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        # nCr 에서  r = 0 , r = len(nums) 일때
        result = [[],nums]


    	# r = 1 ~ len(nums)-1 일때
        for i in range(1,len(nums)):
            result.extend(list(map(list,combinations(nums,i))))

        return result

solution2

• dfs를 이용하기
• 각 원소를 크기 순서대로 부분 집합에 포함시키거나 포함시키지 않는 연산을 수행
• 재귀 과정에 찾은 모든 부분 집합을 결과에 포함
• 더이상 추가할수 있는 원소가 없을때 까지

code2

class Solution(object):
    def subsets(self, nums):

        result = []
        limit = len(nums)

        def dfs(cur=[],idx=0):
            result.append(cur[:])
            if idx >= limit: return
            for i in range(idx, limit):
                cur.append(nums[i])
                dfs(cur,i+1)
                cur.pop()
        dfs()

        return result