77. Combinations

Category	ps/bfs & dfs
Tag	bfs & dfs
Tags	combination
난이도	★★
발행 여부
사이트	Leet code
실수 유형
이해	완벽히 이해
최종 편집 일시	@2021년 12월 10일 오후 10:14
푼 날짜	@2021년 12월 2일 오후 10:33

문제 해설 및 주의사항

원문

번역 및 주의사항

풀이

내 풀이 코드

풀이 코드 (itertools)

퇴고

문제 해설 및 주의사항

원문

Given two integers n and k, return all possible combinations of k numbers out of the range [1, n].

You may return the answer in any order.

Example 1:

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Example 2:

Input: n = 1, k = 1
Output: [[1]]

번역 및 주의사항

[1,n] 범위에서 k 개의 조합을 모두 찾아내어라.

Constraints:

• 1 <= n <= 20

• 1 <= k <= n

---

풀이

내 풀이 코드

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        
        ans = []
        
        def recursive_solve(cnum: int, count: int, ret: list) -> None:
            # 기저사례 : 길이 충족시 return
            if count == k :
                ans.append(ret[:])
                return
            
            for i in range(cnum + 1, n + 1):
                ret.append(i)
                recursive_solve(i, count + 1, ret)
                ret.pop()
        
        recursive_solve(0, 0, [])
        return ans

풀이 코드 (itertools)

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

---

퇴고

• ans.append(ret[:])
  • ret 자체를 append 하면 참조로써 넣기 때문에 문제가 발생한다.
  • [:] 로 깊은 복사를 해주어야 한다.
    • 1차원 배열이기에 [:] 로 충분히 깊은 복사를 이루어 낼 수 있었으나 차원이 높아지면 이 방법으로는 원하는 깊은 복사를 할 수 없으므로,
    • copy.deepcopy 를 이용하자.
      • 실제로 이를 이용해보았더니 슬라이싱보다 살짝 느린 결과가 나온다.

• 파이썬의 itertools.combinations 이용하기
  • 꽤 큰 성능 차이가 난다.