백준 알고리즘
[Silver III] N과 M (1) - 15649
성능 요약
메모리: 13160 KB, 시간: 40 ms
분류
백트래킹
문제 설명
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
use std::io::{BufRead, BufReader, BufWriter, stdin, stdout, Write};
fn go(index: usize, n: usize, m: usize, visited: &mut [bool], ans: &mut [usize], writer: &mut BufWriter<std::io::StdoutLock>) {
if index == m {
writeln!(writer, "{}", ans.iter().map(|&x| x.to_string()).collect::<Vec<_>>().join(" ")).unwrap();
return;
}
for i in 1..=n {
if !visited[i] {
visited[i] = true;
ans[index] = i;
go(index + 1, n, m, visited, ans, writer);
visited[i] = false;
ans[index] = 0;
}
}
}
fn main() {
let mut reader = BufReader::new(stdin().lock());
let mut writer = BufWriter::new(stdout().lock());
let mut input = String::new();
reader.read_line(&mut input).unwrap();
let mut iter = input.trim().split_whitespace();
let n: usize = iter.next().unwrap().parse().unwrap();
let m: usize = iter.next().unwrap().parse().unwrap();
let mut visited = vec![false; n + 1];
let mut ans = vec![0; m];
go(0, n, m, &mut visited, &mut ans, &mut writer);
writer.flush().unwrap();
}
