조합(Combination; 순서 X 중복 X)

순서 X 중복 X

 

서로 다른 n개의 원소 중 r개의 순서없이 골라낸  것

 

https://www.acmicpc.net/problem/15650

 

import java.util.Scanner;

public class Main {
	static int n, m;
	static int[] arr;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		m = sc.nextInt();
		arr = new int[m + 1];

		rec(1);
		sc.close();
	}

	private static void rec(int idx) {
        
		// 기저조건
		if (idx == m + 1) {
			for (int a = 1; a < arr.length; a++) {
				System.out.print(arr[a] + " ");
			}
			System.out.println();
			return;
		}

		// 유도조건
		for (int i = 1; i <= n; i++) {
			if (arr[idx - 1] >= i) { // 직전에 뽑은 수가 지금 수와 같거나 더 크면 지나가기
				continue; // 오름차순으로 뽑고 있기 때문에 중복 거를 수 있음
			}
			arr[idx] = i;  // 직전 수보다 큰 경우에만 뽑아요 -> 중복 불허
			rec(idx + 1);
		}
	}
}

 

** 중복 조합(순서 X 중복 O)

 

https://www.acmicpc.net/problem/15652

import java.util.Scanner;

public class Main {
	static int n, m;
	static int[] arr;
	static StringBuilder sb;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		m = sc.nextInt();
		arr = new int[m + 1];
		sb = new StringBuilder();
		rec(1);
		System.out.println(sb.toString());
		sc.close();
	}

	private static void rec(int idx) {
		// 기저조건
		if (idx == m + 1) {
			for (int a = 1; a < arr.length; a++) {
				sb.append(arr[a]).append(" ");
			}
			sb.append("\n");
			return;
		}

		// 유도조건
		for (int i = 1; i <= n; i++) {
			if (arr[idx - 1] <= i) { // 직전의 수가 현재 수보다 작거나 같으면
				arr[idx] = i; // 뽑아라 -> 중복 허용
                // 직전의 수가 더 큰 경우에는 뽑지 않기 때문에 순서 바꾼 수열을 뽑지 않는 것임
                // 즉 순열이 아닌 조합이라는 의미
			} else {
				continue;
			}
			rec(idx + 1);
		}
	}
}