[백준] 15650번 N과 M - 2 (C++, JAVA)

15650번: N과 M (2)

N개 중에 중복 미 포함, 순서 상관없이 M개를 뽑는 조합 문제이다.

이번엔 check 배열이 필요 없다.

앞의 값보다 큰 값일 경우에만 벡터에 넣어주고 카운트가 M일 때 출력해주면 된다.

 

< C++ 코드 >

#include <iostream>
#include <vector>
using namespace std;
vector <int> v;

int cnt = 0;
void combination(int N, int M, int start) {
	if (cnt == M) {
		for (int i = 0; i < v.size(); i++) {
			cout << v[i] << " ";
		}
		cout << "\n";
	}
	else {
		for (int i = 0; i < N; i++) {
			if (start < i) {
				v.push_back(i + 1);
				cnt++;
				combination(N, M, i);
				v.pop_back();
				cnt--;
			}
		}
	}
}

int main() {
	int N, M;
	cin >> N >> M;
    
	combination(N, M, -1);

	return 0;
}

 

< JAVA 코드 >

import java.util.Scanner;

public class BOJ_15650_N과M_2 {
	public static int N, M;
	public static int arr[];
	
	public static void combination(int cnt, int idx) {
		if(cnt == M) {
			for(int val : arr) System.out.print(val + " ");
			System.out.println();
			return;
		}
		for(int i = idx; i < N; i++) {
			arr[cnt] = i + 1;
			combination(cnt + 1, i + 1);
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); M = sc.nextInt();
		arr = new int[M];
		combination(0, 0);
	}
}