[leetcode / 77] Combinations

in Problem Solving on leetcode


날짜: 2021년 8월 30일
카테고리: 그래프
태그: Medium, 77, 파이썬

leetcode 77 - Combinations

입출력 예시

예제 입력예제 출력
n = 4, k = 2[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]
n = 1, k = 1[[1]]

코드

class Solution:
    def combine(self, n, k):
        answer = list()

        def dfs(elements, start, k):
            if k == 0:
                answer.append(elements[:])
                return

            for i in range(start, n + 1):
                elements.append(i)
                dfs(elements, i + 1, k - 1)
                elements.pop()

        dfs([], 1, k)
        return answer
파이썬 알고리즘 인터뷰 12-4

풀이 과정

전반적인 흐름은 이전의 순열 문제와 같다

answer 리스트 생성
dfs 중첩 함수 생성

  • 만약 k가 0이라면 answer리스트에 elements 리스트를 원소로 추가 후 반환
    • (파이썬은 모든 객체를 참조하는 형태로 처리되므로 얕은 복사를 위해 [:]를 붙여준다.)
  • start부터 n+1까지 반복을 하는데

    • elements 리스트에에 i를 추가하고

    • elements에 대하여 i+1부터 k-1까지의 dfs 함수를 재귀

    • elements의 원소를 pop

빈 리스트에 대하여 1부터 k까지의 dfs 함수 호출

answer을 반환하면 순열들을 리스트 형태로 원소로 가진 리스트가 반환 됨

반성



© 2021. by hminkim