๋ฌธ์
https://www.acmicpc.net/problem/15654
๋ฐฑ์ค ๋ฌธ์ ์ง - 0x0C๊ฐ - ๋ฐฑํธ๋ํน
์๊ณ ๋ฆฌ์ฆ: ๋ฐฑํธ๋ํน
ํ์ด
N๊ฐ์ ์์ฐ์์ ์์ฐ์ M์ด ์ฃผ์ด์ก์ ๋, ์๋ ์กฐ๊ฑด์ ๋ง์กฑํ๋ ๊ธธ์ด๊ฐ M์ธ ์์ด์ ๋ชจ๋ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
N๊ฐ์ ์์ฐ์๋ ๋ชจ๋ ๋ค๋ฅธ ์์ด๋ค.
๋ฐฑํธ๋ํน์ผ๋ก ์์ด(permutation)์ ๋ง๋๋ ๋ฌธ์ ๋ค.
์์ด์ n๊ฐ์ ์ซ์ ์ค์์ ์์๋ฅผ ๊ณ ๋ คํ์ฌ r๊ฐ๋ฅผ ๋ฝ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ๋งํ๋ค.
permutations ๋ชจ๋์ ์ฌ์ฉํ๋ฉด ๋ ๊ฐ๋จํ๊ฒ ์ง๋ง, '๋ฐฑํธ๋ํน' ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ๋๊น ์ ์๋๋ก ํ์๋คใ
ใ
์ ์ฒด ์ฝ๋
# ๋ฉ๋ชจ๋ฆฌ: 31120KB / ์๊ฐ: 152ms
from sys import stdin
input = stdin.readline
N, M = map(int, input().split())
nums = sorted(map(int, input().split()))
def backtrack(ret):
if len(ret) == M:
print(" ".join(map(str, ret)))
return
for i in range(N):
if nums[i] in ret:
continue
ret.append(nums[i])
backtrack(ret)
ret.pop()
backtrack([])
๋จผ์ ๋น ๋ฆฌ์คํธ๋ฅผ ๋ฃ์ด ํจ์๋ฅผ ์คํํ๊ณ , ๊ธธ์ด๊ฐ M์ด ๋ ๋๊น์ง ์ซ์๋ฅผ appendํ๋ค.
๋จ, ์ซ์๊ฐ ์ค๋ณต๋๋ฉด ์๋๋ฏ๋ก ๋ง์ฝ ํ์ฌ ์ซ์๊ฐ ์ด๋ฏธ ๋ฆฌ์คํธ์ ์กด์ฌํ๋ค๋ฉด ๋์ด๊ฐ๋ค.
๋ํ ๊ฒฐ๊ณผ๊ฐ์ ์ค๋ฆ์ฐจ์์ผ๋ก ์ถ๋ ฅํด์ผํ๊ธฐ ๋๋ฌธ์ ํจ์ ์คํ ์ ์ ์ซ์ ๋ฆฌ์คํธ๋ฅผ ์ ๋ ฌํด์ค์ผ ํ๋ค.