[leetcode] combinations

combinations

• n, k ( n >= k >= 1) 의 정수가 주어질때
• n 개의 정수 (1 ~ n) 에서 k 개의 수를 뽑는 조합을 리턴

Solution1

• itertools의 combinations 이용

code1

from itertools import combinations
class Solution(object):
    def combine(self, n, k):
        return list(map(list,combinations(range(1,n+1),k)))

Solution2

• dfs(selected:list,start:int)
• selected에 el 이 추가된 경우 다음의 dfs에서 start = el + 1
• 종료조건 len(selected) == k

code2

class Solution(object):
    def combine(self, n, k):

        results = []

        def dfs(selected, start):
        	
            size = len(selected)
            
            if size == k:
                results.append(selected[:])

            for el in range(start, n + 1):
            	# 현재 선택된 개수 + 나머지 후보 개수 < k 이 될때부터는 탐색 불필요
            	if size + n-el+1 < k : break
                selected.append(el)
                dfs(selected, el + 1)
                selected.pop()

        dfs([], 1)

        return results