1. 순열(Permutation)

서로 다른 n개의 원소 중에서 순서를 고려하여 r개를 선택해 나열하는 모든 경우의 수

예를 들어 'A', 'B', 'C' 세 개의 원소에서 두 개를 선택하여 나열하는 경우, 가능한 순열은 'AB', 'BA', 'AC', 'CA', 'BC', 'CB 총 6가지이다. 순서를 고려하기 때문에 'AB'와 'BA'는 다른 경우의 수가 된다.

public class Main{

	public static void main(String[] args) {
		int arr[] = {1,2,3};
		int path[] = new int[arr.length];
        int r = 2;
		boolean used[] = new boolean[r];	
		permutation(arr, path, used, 0, r);
	}
	
	public static void permutation(int[] arr, int[] path, boolean[] used, int level, int r) {
		if (level == r) {
            // 출력 첫 번째 방법
			for (int i=0; i<r; i++) {
				System.out.print(path[i]);
			}
            // 출력 두 번째 방법
            for (int num: path) {
				System.out.print(num);
			}
			System.out.println();
			return;
		}
		
		for (int i=0; i<arr.length; i++) {
			if (!used[i]) {
				used[i] = true;
				path[level] = arr[i];
				permutation(arr, path, used, level+1, r);
				used[i] = false;
				
			}
		}
	}
}

2. 중복 순열

서로 다른 n개의 원소 중에서 순서를 고려하여 중복이 가능하게 r개를 선택해 나열하는 모든 경우의 수

예를 들어, 'A', 'B', 'C' 세 개의 원소에서 두 개를 선택하여 나열하는 경우, 가능한 중복 순열은 'AA', 'AB', 'AC', 'BA', 'BB', 'BC', 'CA', 'CB', 'CC'로 총 9가지이다. 순열과 마찬가지로 순서가 있기 때문에 'AB'와 'BA'는 다른 경우의 수가 된다.

public class Main {

	public static void main(String[] args) {
		int arr[] = {1,2,3};
        int r = 2;	
		int path[] = new int[r];
		permutation(arr, path, 0, r);
	}
	
	public static void permutation(int[] arr, int[] path, int level, int r) {
		if (level == r) {
            // 출력 첫 번째 방법
			for (int i=0; i<r; i++) {
				System.out.print(path[i]);
			}
			System.out.println();
			return;
		}
		
		for (int i=0; i<arr.length; i++) {
				path[level] = arr[i];
				permutation(arr, path, level+1, r);

		}
	}
}

3. 조합(Combination)

서로 다른 n개의 원소에서 순서 없이 r개를 선택하는 경우의 수

예를 들어, 'A', 'B', 'C' 세 개의 원소에서 두 개를 선택하는 경우, 가능한 조합은 'AB', 'AC', 'BC'로 총 3가지이다. 순서가 없기 때문에 'AB'와 'BA'는 같은 경우의 수가 된다.

public class Main {

	public static void main(String[] args) {
		int arr[] = {1,2,3};
		boolean used[] = new boolean[arr.length];
		int r = 2;		
		combination(arr, used, 0, 0, r);
	}
	
	public static void combination(int[] arr, boolean[] used, int start, int level, int r) {
		if (level == r) {
			for (int i=0; i<arr.length; i++) {
				if (used[i]) {					
					System.out.print(arr[i]);
				}
			}
			System.out.println();
			return;
		}
		
		for (int i=start; i<arr.length; i++) {
			if (!used[i]) {
				used[i] = true;
				combination(arr, used, i+1, level+1, r);
				used[i] = false;
				
			}
		}
	}
}

4. 중복 조합

서로 다른 n개의 원소에서 순서 없이 중복 가능하게 r개를 선택하는 경우의 수

예를 들어, 'A', 'B', C' 세 개의 원소에서 두 개를 선택하는 경우, 가능한 중복 조합은 'AA', 'AB', AC', 'BB', 'BC', 'CC'로 총 6가지이다. 조합과 똑같이 순서가 없기 때문에 'AB'와 'BA'는 같은 경우의 수가 되고 중복을 허용하므로 'AA', 'BB', 'CC' 경우의 수가 가능하다.

public class TEST {

	public static void main(String[] args) {
		int arr[] = {1,2,3};
        int r = 2;	
		int path[] = new int[r];
		combination(arr, path, 0, 0, r);
	}
	
	public static void combination(int[] arr, int[] path, int start, int level, int r) {
		if (level == r) {
			for (int i=0; i<r; i++) {			
				System.out.print(path[i]);
			}
			System.out.println();
			return;
		}
		
		for (int i=start; i<arr.length; i++) {
			path[level] = arr[i];
			combination(arr, path, i, level+1, r);
		}
	}
}

참고
[알고리즘] 순열, 중복순열, 조합, 중복조합 총정리 !