[c++] 백준 15650, 15651, 15652 N과 M (2), (3), (4)

백준 단계별로 풀어보기 [백트래킹] N과 M (2), (3), (4)

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

15650번: N과 M (2)

 

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

15651번: N과 M (3)

 

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

15652번: N과 M (4)

 

[풀이]

(2). (1)이 순열을 출력하는 문제였다면, (2)는 조합을 출력하는 문제이다. (1, 2)와 (2, 1)을 구분해야하므로 num을 전달해서 반복문이 이전 값을 고려하지 않도록 해준다.

(3). 같은 수를 여러번 골라도 되기때문에 방문했는지 여부를 체크하지 않는다.

(4). (2)와 (3)의 조건을 모두 포함한다.

 

[코드]

(2) 조합 출력

#include <iostream>
#include <algorithm>
#define MAX 9

int n, m;
bool visited[MAX] = { false, };
int list[MAX];

void dfs(int num, int count) {
	if (count == m) {
		for (int i = 0; i < m; i++) {
			std::cout << list[i]+1 << " ";
		}
		std::cout << "\n";
		return;
	}

	for (int i = num; i < n; i++) {
		if (!visited[i]) { 
			visited[i] = true;
			list[count] = i;
			dfs(i+1, count+1);
			visited[i] = false; 
		}
	}

}

int main() {
	std::cin >> n >> m;
	dfs(0, 0);

	return 0;
}

(3) 자기 자신 포함

#include <iostream>
#include <algorithm>
#define MAX 9

int n, m;
bool visited[MAX] = { false, };
int list[MAX];

void dfs(int count) {
	if (count == m) {
		for (int i = 0; i < m; i++) {
			std::cout << list[i] << " ";
		}
		std::cout << "\n";
		return;
	}

	for (int i = 1; i <= n; i++) {
		list[count] = i;
		dfs(count+1);
	}

}

int main() {
	//자기 자신도 출력
	std::cin >> n >> m;
	dfs(0);

	return 0;
}

(4) 자기 자신 포함 + 비내림차순

#include <iostream>
#include <algorithm>
#define MAX 9

int n, m;
bool visited[MAX] = { false, };
int list[MAX];

void dfs(int num, int count) {
	if (count == m) {
		for (int i = 0; i < m; i++) {
			std::cout << list[i]+1 << " ";
		}
		std::cout << "\n";
		return;
	}

	for (int i = num; i < n; i++) {
		list[count] = i;
		dfs(i, count+1);
	}

}

int main() {
	//자기 자신을 출력하되, 비내림차순으로.
	std::cin >> n >> m;
	dfs(0, 0);

	return 0;
}