[백준 15650] N과 M (2)

🍎[백준 15650] N과 M (2) 

문제링크

https://www.acmicpc.net/problem/15650

15650번: N과 M (2)

 

⚾ 코드

# 조합 직접 구현

from itertools import combinations

n, m = map(int, input().split())
cnt = m
numbers = list(range(1, n+1))

# res = []


def combination(pre, now, m):
    if len(now) < m or m == 0:
        return pre

    for i in range(len(now)):
        pre.append(now[i])
        temp = combination(pre, now[i+1:], m-1)
        if temp and len(temp) == cnt:
            # res.append(temp[:])
            print(*temp)
        pre.pop()


combination([], numbers, m)

 

🔔 해결 과정 & 깨달은 점

- itertools의 permutations를 쓰지 않고 순열을 직접 구현해보고 싶었다.

 

- 구현한 원리는 다음과 같다.

- 순열의 경우와 비슷하지만, 한 번 뽑은 숫자는 다시 뽑지 않아도 된다는 점이 다르다.

 

예를 들어 1,2,3,4 중에서 중복없이 2개를 뽑아 조합을 구한다고 하자.

잘 생각해보면 1, 2, 3, 4에서 2개를 뽑는 것은 1을 뽑고 2, 3, 4중에서 1개를 뽑는 경우의 수와 2를 뽑고 1, 3, 4중에서 1개를 뽑는 경우의 수와 3을 뽑고 4 중에서 1개를 뽑는 경우의 수를 합한것과 같다.

식으로 나타내자면

combination([], [1, 2, 3, 4], 2) = combination([1], [2, 3, 4], 1) + combination([2], [3, 4], 1) + combination([3], [4], 1)이다.

 

백트래킹의 원리로 풀 수 있다.

 

순열과 마찬가지로 종료 조건은 m이 0이 되거나 현재 탐색해야 하는 숫자의 길이보다 작을 때 종료된다.