15650번: N과 M(2)

15650번: N과 M (2)

 

백트래킹 문제다.

 

이번에는 1부터 N까지 자연수 중 중복없이 M개를 고르지만,

고른 수열은 오름차순이어야 한다는 조건이 있다.

 

---

# 15650번: N과 M(2)


n, m = map(int, input().split())

result = []
def backTracking(num, x):
    if num == m:
        print(" ".join(map(str, result)))
        return

    for i in range(x+1, n+1):
        if i not in result:
            result.append(i)
            backTracking(num + 1, i)
            result.pop()

backTracking(0, 0)

 

backTracking함수에서 num 파라미터는 현재까지의 result 리스트의 길이를 의미한다.

그리고 x를 통해 result 리스트에 값을 넣어주는데, for문의 초기값에 넣어주어 결국 전에 들어간 숫자보다 큰 숫자만 result 리스트에 들어가게 된다.

 

굳이 파라미터를 2개 쓰지 않고 x만 써서 푸는 방법도 있다.

 

# 15650번: N과 M(2)


n, m = map(int, input().split())

result = []
visted = [False] * (n+1)
def backTracking(x):
    if len(result) == m:
        print(" ".join(map(str, result)))
        return

    for i in range(x+1, n+1):
        if i not in result:
            result.append(i)
            backTracking(i)
            result.pop()

backTracking(0)

 

이렇게 풀어도 된다.