[백준][파이썬] 15651 N과 M (3)

1.문제 분석

• 1부터 n까지의 자연수 중 중복을 포함하여 m개의 수를 고른다.
• 백트래킹을 사용하는 문제

---

2. 기본 아이디어

1.  N과 M (1)번 문제에서 if not i in lst 구문 대신 len(lst) != m 구문을 넣는다.

---

3.문제 풀이

 

len(lst) != m 구문은 리스트의 길이가 m이 되기 전까지 재귀를 반복한다.

따라서 리스트의 길이가 m이 되었을 때 중복 상관없이 출력할 수 있게 된다.

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

lst = []

def BackTracking():

    if len(lst) == m:
        print(" ".join(map(str, lst)))

    for i in range(1, n + 1):
        if len(lst) != m:
            lst.append(i)
            BackTracking()
            lst.pop()

BackTracking()