03/11 코딩테스트 문제풀이 - 77. Combinations (Leetcode) ⭐⭐⭐⭐⭐

문제

• Leetcode 알고리즘 문제
• 46. Permutations (Medium)
• 문제 내용 : [링크]
  
  

내가 작성한 코드

class Solution:
    def combine(self, n, k):
        def backtrack(s, path):
            if len(path) == k:
                result.append(path)
                return

            for i in range(s, n+1):
                if i not in path:
                    path.append(i)
                    backtrack(i+1, path[:])
                    path.pop()



        result = []
        backtrack(1, [])
        return result

• n, k가 주어질 때 [1,n]의 범위에서 k개를 선택할 수 있는 조합(Combination)을 구하는 문제이다.(중복이 없는 비복원추출)

• k번의 반복을 해야하나, for문으로는 구현하기 어렵다. 따라서 backtrack 을 활용한 완전탐색으로 문제를 시작

• backtrack(s, path) 함수를 구현해준다. 만약 path (즉, 하나의 조합)의 길이가 k인 경우, 이미 k개를 선택했으므로 result에 append 하고 return 해 준다.

• len(path) != k인 경우, for문을 통해 s부터 n까지 숫자중 하나를 선택해준다. 이 때 path에 없는 숫자인 경우, path.append(i) 해 준다.

• 다음 숫자를 뽑을 때에는 s+1 ~ n까지 숫자 중 하나를 선택해야 하므로, backtrack(i+1, path[:]) 해 준다.

• 하나의 조합이 완성된 경우(즉, path에 k개의 숫자를 선택한 경우)
  path.pop() 해 주어 다음 조합을 만들어나간다. 이 과정을 반복한다.

• 첫 함수 시작을 backtrack(1, [])을 실행해준다.

• 모든 조합이 담긴 result를 return 해준다.

⭐⭐⭐⭐⭐

• 완전탐색의 기초가 되는 아주 중요한 문제! 계속 반복해서 풀어보기.