[백준] 15666_N과 M(12) (Python)

15666_N과 M(12)(Python)

0. 출처

• 유형 : 백트래킹 (silver 2)
• 링크 : 15666번: N과 M(12)

1. 기록

• 22/04/03 (일)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 주어진 수에 '중복된 숫자가 있을 때' 중복조합을 구하는 문제
>> set 이용 중복된 수를 제거하고 중복조합을 구한다.

2. 시간복잡도
>>

3. 자료구조
>>
'''

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
3 1
4 4 2

- 예제 출력 1 -
2
4

- 예제 입력 2 -
4 2
9 7 9 1

- 예제 출력 2 -
1 1
1 7
1 9
7 7
7 9
9 9

(3) 코드

n, m = map(int, input().split())
nums = list(map(int, input().split()))
nums = set(nums)
nums = list(nums)
nums = sorted(nums)

stack = []

def iterative_dfs(start):
    if len(stack) == m:
        print(*stack)
        return

    for i in range(start, len(nums)):
        stack.append(nums[i])
        iterative_dfs(i)
        stack.pop()

iterative_dfs(0)

(4) 정리

(5) 참고