[Backtracking] Leetcode 77. Combination

khy__·2021년 12월 22일
0

알고리즘

목록 보기
2/3
post-thumbnail

Backtracking 이란?

백트래킹(backtracking)이란?

해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말한다. 최적화 문제와 결정 문제를 푸는 방법이다. 대표적인 문제로 n-queens 문제가 있다. 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 뜻이다.

  • 즉, 백트래킹은 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것이다.
  • 답이 될 만한지 판단하고 그렇지 않으면 그 부분까지 탐색하는 것을 하지 않고 가지치기 하는 것이다.
  • 주로 문제 풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문 등을 걸어 답이 절대로 될 수 없는 상황을 정의하고, 그러한 상황일 경우에는 탐색을 중지시킨 뒤 그 이전으로 돌아가서 다시 다른 경우를 탐색하게끔 구현할 수 있다.
    출처: 알고리즘 - 백트래킹(Backtracking)의 정의 및 예시문제

문제

문제 링크: Leetcode - 77.Combinations

77. Combinations

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]]

Constraints:

  • 1 <= n <= 20
  • 1 <= k <= n

풀이

1. 백트래킹을 이용한 풀이

# backtracking
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        solution = []

        def backtrack(k, combination, next):
            if k == 0:
              # 3. 만약 combination 안에 숫자가 k개 다 찾다면, 해당 combination을 solution 배열에 넣는다.
                solution.append(combination.copy())
            else:
                for i in range(next, n + 1):
                    # 1. combination에 테스트할 숫자를 넣어준다. 숫자 하나 들어갈때 마다 총 숫자 (k) 를 하나씩 줄인다.
                    combination.append(i)
                    # 2. next 값인 i 를 하나 올려서 다시 backtracking 시작
                    backtrack(k - 1, combination, i + 1)
                    # 4. k == 0 까지 갔다면, combination 마지막에 있던 숫자를 빼고 새로운 숫자 넣고 다시 시작한다.
                    combination.pop()
        
        backtrack(k, [], 1)
        return solution

2. 라이브러리를 이용한 풀이

# python combination 라이브러리 사용
from itertools import combinations

class Solution:
    def combine(self, n, k):
        return list(combinations(range(1, n+1), k))

참고

0개의 댓글