[BOJ] 15657_N과 M (8) with cpp

# 생각

1. N개의 자연수 중에서 M개를 고른 수열

--> 조합의 개수를 구하는 문제

--> backtracking

 

2. 같은 수를 여러 번 골라도 된다

--> 해당 수의 사용 유무를 저장하여 걸러낼 필요가 없다

 

3.  고른 수열은 비 내림차순이어야 한다

--> 시작 지점을 이전에 고른 수로 설정하여

--> 다음에 선택할 수가 이전에 고른 수 보다 크거나 같아야 한다

 

1부터 n까지 수에 대해 사용되지 않은 수가 있다면 그 수를 넣고

다음 수를 정하는 함수를 재귀방식으로 작성한다

 

 

# 전체 코드

// 1s, 512MB
// 1 <= M <= N <= 8
#include <bits/stdc++.h>
using namespace std;

int arr[8];
int num[8];

void funcRecursive(int k, int n, int m)
{
	if (k == m)
	{
		for (int i = 0; i < m; i++)
		{
			cout << num[arr[i]] << ' ';
		}
		cout << '\n';
		return;
	}
	int st = 0;
	if (k != 0) st = arr[k - 1];
	for (int i = st; i < n; i++)
	{
		arr[k] = i;
		funcRecursive(k + 1, n, m);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> num[i];
	}
	sort(num, num + n);
	funcRecursive(0, n, m);
}

 

---

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

15657번: N과 M (8)