Java 순열 조합 재귀

자바 순열 조합 구현

순열

N개 중에 R개 뽑아서 각각의 경우마다 처리해야 하는 로직이 있다. 이때 뽑는 순서에 따라 결과가 달라진다.

String[] arr;
int N, R;
int[] selection;
boolean[] visited;
int cnt;

void solution() {

	arr = new String[] {"A", "B", "C", "D"};
	N = arr.length;
	R = 2;
	selection = new int[R];
	visited = new boolean[N];

	recursive(0);

	System.out.println(cnt);

}

void recursive(int r) {

	if (r == R) {
		logic();
		cnt++;
		return;
	}

	for (int n = 0; n < N; n++) {
		if (visited[n]) continue;
		selection[r] = n;
		visited[n] = true;
		recursive(r + 1);
		visited[n] = false;
	}

}

void logic() {
	for (int i = 0; i < R; i++) {
		System.out.print(arr[selection[i]] + " ");
	}
	System.out.println();
}

조합

N개 중에 R개 뽑아서 각각의 경우마다 처리해야 하는 로직이 있다. 이때 뽑는 순서는 결과에 영향이 없다.

String[] arr;
int N, R;
int[] selection;
int cnt;

void solution() {

	arr = new String[] {"A", "B", "C", "D"};
	N = arr.length;
	R = 2;
	selection = new int[R];

	recursive(0, 0);

	System.out.println(cnt);

}

void recursive(int n, int r) {

	if (r == R) {
		logic();
		cnt++;
		return;
	}

	for (int i = n; i < N; i++) {
		if (N - i < R - r) continue;
		selection[r] = i;
		recursive(i + 1, r + 1);
	}

}

void logic() {
	for (int i = 0; i < R; i++) {
		System.out.print(arr[selection[i]] + " ");
	}
	System.out.println();
}