[2022.04.14.] N과 M (6)

문제 정보

링크: https://www.acmicpc.net/problem/15655

난이도: Silver III

분류: [재귀 → 백트래킹]

 

문제 요약

\( N \)개의 수가 주어질 때, \( M \)개를 중복없이 선택해서 만들 수 있는 모든 조합을 찾으면 됩니다.

 

풀이

오름차순으로 정렬된 수열을 출력해야 하니, 들어온 수들을 오름차순 정렬해봅시다.

 

이제 남은 건 백트래킹으로, \( M \)개를 "중복 없이" 고르는 걸 시뮬레이션해주면 됩니다.

이는 "마지막으로 선택한 원소의 위치"를 저장한 뒤, 이보다 더 오른쪽에 있는 원소만을 골라주면 됩니다.

int n, m;
int arr[10];

int res[10];
void btk(int cnt, int idx){
	if (cnt == m){
		for (int i = 0; i < cnt; i++){ cout << res[i] << ' '; }
		cout << endl; return;
	}
	for (int i = idx; i <= n; i++){
		res[cnt] = arr[i]; btk(cnt+1, i+1);
	}
}

void Main(){
	cin >> n >> m;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	sort(arr+1, arr+n+1);
	btk(0, 1);
}