조합

배열 요소 뽑아내기

import java.util.*;

public class Main {
	public static void main(String[] args) {
		int r = 3;
		int[] a = {1, 2, 3, 4};
		combinations(a, r);
		System.out.println();
	}

	public static void combinations(int[] a, int r) {
        r = Math.min(r, a.length);
        combinations(a, new int[r], 0, 0, a.length, r);
	}

	private static void combinations(int[] a, int[] b, int aIdx, int bIdx, int n, int r) {
		if(bIdx == r) {
			System.out.println(Arrays.toString(b));
			return;
		}

		for(int i = aIdx; i < n; i++) {
			b[bIdx] = a[i];
			combinations(a, b, i + 1, bIdx + 1, n, r);
		}
	}

}

배열 인덱스 뽑아내기

import java.util.*;

public class Main {
	public static void main(String[] args) {
		int n = 5, r = 3;
		combinations(n, r);
		System.out.println();
	}

	public static void combinations(int n, int r) {
        r = Math.min(n, r);
        combinations(new int[r], 0, 0, n, r);
	}

	private static void combinations(int[] b, int aIdx, int bIdx, int n, int r) {
		if(bIdx == r) {
			System.out.println(Arrays.toString(b));
			return;
		}

		for(int i = aIdx; i < n; i++) {
			b[bIdx] = i;
			combinations(b, i + 1, bIdx + 1, n, r);
		}
	}

}

중복조합

배열 요소 뽑아내기

import java.util.*;

public class Main {
	public static void main(String[] args) {
		int r = 3;
		int[] a = {1, 2, 3, 4};
		combinations(a, r);
		System.out.println();
	}

	public static void combinationsWithRepetition(int[] a, int r) {
        r = Math.min(r, a.length);
        combinationsWithRepetition(a, new int[r], 0, 0, a.length, r);
	}

	private static void combinationsWithRepetition(int[] a, int[] b, int aIdx, int bIdx, int n, int r) {
		if(bIdx == r) {
			System.out.println(Arrays.toString(b));
			return;
		}

		for(int i = aIdx; i < n; i++) {
			b[bIdx] = a[i];
			combinationsWithRepetition(a, b, i, bIdx + 1, n, r);
		}
	}

}

aIdx에 i + 1 주는 걸 i로 바꾸면 끝.
그냥 자기 자신도 포함시키면 끝이다.

배열 인덱스 뽑아내기

import java.util.*;

public class Main {
	public static void main(String[] args) {
		int n = 5, r = 3;
		combinationsWithRepetition(n, r);
		System.out.println();
	}

	public static void combinationsWithRepetition(int n, int r) {
        r = Math.min(n, r);
        combinationsWithRepetition(new int[r], 0, 0, n, r);
	}

	private static void combinationsWithRepetition(int[] b, int aIdx, int bIdx, int n, int r) {
		if(bIdx == r) {
			System.out.println(Arrays.toString(b));
			return;
		}

		for(int i = aIdx; i < n; i++) {
			b[bIdx] = i;
			combinationsWithRepetition(b, i, bIdx + 1, n, r);
		}
	}

}