[백준 15652] N과 M (4)

● 문제 : 백준 15652번 : N과 M (4)

15652번: N과 M (4)

 

● 알고리즘

- 재귀함수

- 백트래킹

[백트래킹]

 

● 문제 풀이

백준 15650번 N과 M (2) 코드에서 조금만 수정하면 된다.

[백준 15650] N과 M (2)

백준 15650번 N과 M (2) 문제가 중복을 허용하지 않는 조합을 구하는 것이라면, 이 문제는 중복을 허용하는 조합을 구하는 것이다. (1,1)과 같은 수열도 허용한다는 것이다. 따라서, 백트래킹을 위한 조건인 방문했는지를 검사하는 단계가 필요없어진다. 그러므로 N과 M (2) 코드에서 if (visit[i] == 0) 구문만 없애주고, 호출하는 재귀함수의 start에 해당하는 첫 번째 매개변수를 DFS(i, cnt + 1)로 바꿔주면 된다.

 

● 코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <algorithm>
#include <string>
#include <cstring>
#include <climits>
#include <random>
#include <cmath>
#include <set>
#include <ctime>
using namespace std;
using ll = long long;
using ii = pair<int, int>;

int N, M;
vector<int>arr;
vector<int>visit(9);
void DFS(int start, int cnt)
{
	if (cnt == M)
	{
		for (int i = 0; i < arr.size(); i++)
			cout << arr[i] << " ";
		cout << "\n";
		return;
	}

	for (int i = start; i <= N; i++)
	{
		visit[i] = 1;
		arr.push_back(i);
		DFS(i, cnt + 1);
		visit[i] = 0;
		arr.pop_back();
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> N >> M;
	DFS(1, 0);
	return 0;
}