조합 (Combination)

class Combination{
	
	static char[] arr;
	static int N;
	static int R;
	
	static int[] select; // 선택idx 저장변수 
	static boolean[] isSelected; // 마킹배열 
	
	
	public static void main(String[] args) {
		
		arr = new char[] {'A' ,'B','C','D'};
		//초기화 
		N = arr.length;
        R = 2;
        isSelected = new boolean[N]; 
        select = new int[R];
        
        combination(0,0);
        
        
}

	static void combination(int idx, int size) { // size : 몇개 선택되었나?
		//종료조건 
		if(size == R) {
			for (int i = 0; i < R; i++) {
				System.out.print(arr[select[i]]);
			}
			System.out.println();
			return;
		}
		
		//재귀확장 
		
		for (int i = idx; i < N; i++) { // idx 부터 N까지 탐색
			if(isSelected[i]) continue;
			
			isSelected[i] = true;
			select[size] = i; // 몇번째 인덱스가 저장되었나
			
			combination(i, size+1); // 하나 선택했으니까 사이즈 올려서 재귀 
			
			isSelected[i] = false;
		}
	}
}

결과

AB
AC
AD
BC
BD
CD

순열(Permutation)

public class Permutation {

	static char[] arr; // 문자열 배열
	static int N; // 배열 크기
	static int[] select; // 선택 저장 변수
	static boolean[] isSelected; // 마킹 배열

	public static void main(String[] args) {

		arr = new char[]{'A', 'B', 'C', 'D'};
		N = arr.length;
		select = new int[N];
		isSelected = new boolean[N];

		permutation(0);
	}

	// 순열 구하는 재귀 함수
	static void permutation(int idx) {

		// 종료 조건: 모든 자리에 원소가 채워졌을 때
		if (idx == N) {
			for (int i = 0; i < N; i++) {
				System.out.print(arr[select[i]]);
			}
			System.out.println();
			return;
		}

		// 재귀 확장 //
		for (int i = 0; i < N; i++) {
			// 이미 선택된 원소라면 건너뜀
			if (isSelected[i]) {
				continue;
			}

			// 현재 자리에 원소 선택
			isSelected[i] = true;
			select[idx] = i;

			// 다음 자리에 대한 순열 재귀 호출
			permutation(idx + 1);

			// 선택 해제 (다음 원소 선택을 위해)
			isSelected[i] = false;
		}
	}
}

결과

ABCD
ABDC
ACBD
ACDB
ADBC
ADCB
BACD
BADC
BCAD
BCDA
BDAC
BDCA
CABD
CADB
CBAD
CBDA
CDAB
CDBA
DABC
DACB
DBAC
DBCA
DCAB
DCBA

부분집합 (Subset)

public class SubSetTest {

	static char [] arr;				// 문자열 배열
	static int N;					// 배열 크기
	static boolean [] isSelected;	// 마킹 배열
	
	public static void main(String[] args) {
		
		arr = new char [] {'A' , 'B' , 'C' , 'D'};
		N = arr.length;
		isSelected = new boolean [N];
		
		subset(0);
	}

	// 부분집합 구하는 재귀함수
	static void subset(int idx) {

		// 종료조건
		if(idx == N) {
			for (int i = 0; i < N; i++) {
				if (isSelected[i])
					System.out.print(arr[i] + " ");
			}
			System.out.println();

			return;
		}
		// 재귀 확장 //

		// 1). 선택하는 경우
		isSelected[idx] = true;
		subset(idx + 1);

		// 2). 선택하지 않는 경우
		isSelected[idx] = false;
		subset(idx + 1);
	}
	
}

결과

A B C D 
A B C 
A B D 
A B 
A C D 
A C 
A D 
A 
B C D 
B C 
B D 
B 
C D 
C 
D