리트코드 - 조합

과정

• 순열은 가능한 모든 경우의 수를 모두 포함하지만 조합은 중복된 요소들은 제거한다.
• 순열은 순서를 보지만 조합은 순서를 보지 않는다.

풀이

• 시간 초과(순열 풀이로 중복만 제거하려고 함.)

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        results = []
        prev_elements = []

        def dfs(elements):
            if len(prev_elements) == k:
                results.append(prev_elements[:])
                return

            for i in elements:
                next_elements = elements[:]
                next_elements.remove(i)

                prev_elements.append(i)
                dfs(next_elements)
                prev_elements.pop()

        nums = []
        for i in range(n):
            nums.append(i + 1)
        dfs(nums)

        for i in results:
            i.sort()
        # print(list(set(tuple(map(tuple, results)))))

        return list(set(tuple(map(tuple, results))))

• 시간 통과

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        results = []
        prev_elements = []

        def dfs(elements):
            # base case
            if len(prev_elements) == k:
                results.append(prev_elements[:])
                return

            # recursion case
            for i, element in enumerate(elements):
                next_elements = elements[i + 1:]
                prev_elements.append(element)

                dfs(next_elements)
                prev_elements.pop()

        nums = []
        for i in range(n):
            nums.append(i + 1)

        dfs(nums)
        return results**텍스트**

reference

파이썬 알고리즘 인터뷰