[BOJ] 백준 15649 N과 M (1) (Swift)

문제

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

15649번: N과 M (1)

풀이

1부터 n까지 자연수 중에서 중복없이 m개를 고른 수열을 모두 출력하는 문제입니다.

백트래킹 알고리즘을 사용하여 풀 수 있습니다.
이미 뽑은 수는 제외하기 위해 visited라는 [Bool] 자료형을 사용하였습니다.

1부터 n까지 for문을 돌면서, 아직 선택하지 않은 수라면 배열에 넣어주고
visited 배열을 사용하여 선택했다는 표시를 해주고, 재귀함수 형태로 다시 1부터 n까지 for문을 돌도록 구현하였습니다.
m개를 고른 경우에는 함수를 return 하고, 직전에 골랐던 수를 선택 해제를 해주었습니다.

소스코드

후기

백트래킹 알고리즘을 처음 접해보았다면 코드의 흐름을 알기가 약간 까다로울 수 있는 문제인 것 같습니다.
벡트래킹에 대한 이해가 있다면 쉽게 풀 수 있습니다.
백트래킹 알고리즘의 기초 문제인 것 같습니다.