35. Combinations

🎯 leetcode - 77. Combinations

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 35번 문제
- 모든 조합 구하기

📌 날짜

2020.02.05

📌 시도 횟수

2 try

💡 Code

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def dfs(curr):
            if len(path) == k:
                result.append(path[:])
                return

            for num in curr:
                next = nums[nums.index(num) + 1 :]
                path.append(num)
                dfs(next)
                path.pop()

        result, path = [], []
        nums = [i for i in range(1, n + 1)]
        dfs(nums)

        return result

💡 문제 해결 방법

- 34번 문제(순열)와 비슷한 방법으로 풀었다.
- 단, 순열과는 다르게 조합의 경우 자기 자신뿐 아니라 현재 값 앞의 모든 요소를
배제하고 next를 구성하였다. 그리고 이 next가 다시 다음 재귀때 curr로 사용되도록 했다.
- 순열과 마찬가지로 path에 담긴 숫자 요소의 개수가 k와 같아지면 result에 담고 리턴한다.
- 리턴하면서 path.pop()이 실행되어 path에 담긴 요소가 한 개씩 pop된다.
- 순열과 마찬가지로 참조로 처리되지 않도록 path를 처리할때에는 [:] 연산자로 값 자체를 복사해 추가했다.

💡 새롭게 알게 된 점

- list.index(idx) : list에서 인덱스가 idx인 요소의 값을 리턴한다.

❌ (한번에 맞추지 못한 경우) 오답의 원인

-

---

😉 다른 풀이

📌 하나. DFS로 조합 만들기

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def dfs(elements, start: int, k: int):
            if k == 0:
                result.append(elements[:])
                return

            for i in range(start, n + 1):
                elements.append(i)
                dfs(elements, i + 1, k - 1) # 자신 이후의 값들을 전달, k-- 하기
                elements.pop()

        result = []
        dfs([], 1, k)

        return result

💡 문제 해결 방법

✔ 방법
- <조합의 경우 순열과 달리 자기 자신뿐 아니라 현재 값 앞의 모든 요소를 배제하고 next를 구성>한다.
- 즉, 애초에 nums라는 숫자 list를 만들어 슬라이싱을 할 필요가 없고,
매 재귀때 for문의 범위를 (이전 값의 인덱스+1, n+1)으로 설정하면 되었다. 
- 또한 k(조합의 길이)부터 시작해 재귀될때마다 k-- 해줌으로써 k == 0가 되는 시점에 하나의 
완전한 조합 경우의 수가 생성됨을 알 수 있다.

- 내 방법을 더 효율적으로 구현한 코드인 것 같다.

---

📌 둘. 파이썬의 itertools 모듈 사용

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        return list(itertools.combinations(range(1, n + 1), k))

💡 새롭게 알게 된 점

- itertools.permutations(iterable(, len)) : 순열
- itertools.combinations(iterable, len) : 조합