순열, 조합, 부분집합

순열

import java.util.Arrays;

// nPn
public class PermutationTest {

	static int[] numbers; // 뽑은 수 기억하는 배열.
	static int N = 4; // 입력받는 수로 추후 변경 필요.
	static boolean[] isSelected;

	public static void main(String[] args) {
		numbers = new int[N];
		isSelected = new boolean[N + 1]; // 인덱스 0으로 하거나, 숫자에 맞춰서 +1.
		
		permutation(0);
		
	}

	static void permutation(int cnt) { // 직전까지 뽑은 순열의 개수.
		if (cnt == N) {
			System.out.println(Arrays.toString(numbers));
			return;
		}
		
		for (int i = 1; i <= N; i++) { // i: 시도하는 숫자
			// 선택된 숫자는 시도하면 안 됨. -> 다음 수로 건너뜀.
			if (isSelected[i]) continue;
			
			numbers[cnt] = i; // 현재 뽑은 수를 저장.
			isSelected[i] = true; // 현재 뽑은 수(= 시도하는 숫자) 사용 중으로 체크.
			
			// ++cnt 하면
			permutation(cnt + 1);
			// --cnt 해줘야 하니까 매개변수에서 +1 해줌.
			// 현재 cnt 위치에 i를 선택한 채로 뒤에 만들 수 있는 모든 순열을 만들고 돌아왔다.
			// 현재 자리에 다음 수를 넣으러 가야 하는데 이때 지금 뽑았던 수는 사용하지 않았던 것처럼 돌려놔야 뒤에서 선택 가능해짐.
			isSelected[i] = false;
		}
	}

}

조합

import java.util.Arrays;

// nCr
public class CombinationTest {

	static int[] numbers;
	static int N = 4, R = 2;

	public static void main(String[] args) {
		numbers = new int[R];
		combination(0, 1); // 1부터 뽑으니까, 나중에 입력받은 수로 하면 인덱스 0부터 시작.
	}

	static void combination(int cnt, int start) { // 조합의 선택지의 시작점도 필요.
		if (cnt == R) {
			System.out.println(Arrays.toString(numbers));
			return;
		}
		
		// 처음부터 돌리면 뽑았던 것이 또 나와 중복이 생길 수 있으니까 시작점을 지정해서 중복을 제거.
		for (int i = start; i <= N; i++) { // i : 시도하는 수
			numbers[cnt] = i;
			combination(cnt + 1, i + 1); // 현재 뽑은 i 다음 수
		}
	}
	
}

부분집합

import java.util.Scanner;

public class S1_SubSetTest {

	static int N, totalCnt;
	static int[] input;
	static boolean[] isSelected;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		input = new int[N];
		isSelected = new boolean[N];
		
		for(int i = 0; i < N; i++) {
			input[i] = sc.nextInt();
		}
		generateSubset(0);
		System.out.println("총 경우의 수: " + totalCnt);
	}

	// 현 원소를 부분집합의 구성에 반영
	// cnt는 몇 번째 수인지 확인과 동시에 인덱스로 사용
	private static void generateSubset(int cnt) {
		if (cnt == N) {
			totalCnt++;
			for (int i = 0; i < N; i++) {
				System.out.print((isSelected[i] ? input[i] : "X") + "\t");
			}
			System.out.println();
			return;
		}

		// 순열은 1을 선택했다가 2를 선택하고 돌아오면서 선택했던 1을 취소 -> 다소 헷갈림
		// 부분집합은 순열과 다르게 선택/비선택이라는 2가지의 동작

		// 선택
		isSelected[cnt] = true;
		generateSubset(cnt + 1);
		
		// 비선택
		isSelected[cnt] = false;
		generateSubset(cnt + 1);
	}

}