순열, 조합, 부분집합

순열 - 순서가 있는 열

import java.util.Scanner;

public class Permutation {

    private static boolean[] isSelected;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt(); // nPr -> 'n'
        int R = scanner.nextInt(); // nPr -> 'r'

        isSelected = new boolean[N];
        String[] target = new String[N];
        for (int i = 0; i < target.length; i++) {
            target[i] = scanner.next();
        }

        permutation(target, R, 0, new StringBuilder());
        System.out.println();
        permutationRepetition(target, R, 0, new StringBuilder());
    }

    // 순열
    private static <T> void permutation(T[] target, int R, int count, StringBuilder sb) {
        if (count == R) {
            System.out.println(sb);
            return;
        }

        for (int i = 0; i < target.length; i++) {
            if (!isSelected[i]) {
                isSelected[i] = true; // 현재 이 수를 선택했음
                int currentLength = sb.length(); // 추가 전 StringBuilder 길이 기억
                sb.append(target[i] + " ");
                permutation(target, R, count + 1, sb); // 다음으로
                sb.setLength(currentLength); // 다시 제거
                isSelected[i] = false; // 선택 해제
            }
        }
    }

    // 중복순열
    private static <T> void permutationRepetition(T[] target, int R, int count, StringBuilder sb) {
        if (count == R) {
            System.out.println(sb);
            return;
        }

        for (int i = 0; i < target.length; i++) {
            int currentLength = sb.length();
            sb.append(target[i] + " ");
            permutationRepetition(target, R, count + 1, sb);
            sb.setLength(currentLength);
        }
    }

}

조합 - 순서가 없는 열

import java.util.Scanner;

public class Combination {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt(); // nPr -> 'n'
        int R = scanner.nextInt(); // nPr -> 'r'

        String[] target = new String[N];
        for (int i = 0; i < target.length; i++) {
            target[i] = scanner.next();
        }

        combination(target, 0, R, 0, new StringBuilder());
        System.out.println();
        combinationRepetition(target, 0, R, 0, new StringBuilder());
    }

    // 조합
    private static <T> void combination(T[] target, int start, int R, int count, StringBuilder sb) {
        if (count == R) {
            System.out.println(sb);
            return;
        }

        for (int i = start; i < target.length; i++) {
            int currentLength = sb.length();
            sb.append(target[i] + " ");
            combination(target, i + 1, R, count + 1, sb); // 현재보다 뒤에 있는 위치부터 살핌
            sb.setLength(currentLength);
        }
    }

    // 중복조합
    private static <T> void combinationRepetition(T[] target, int start, int R, int count, StringBuilder sb) {
        if (count == R) {
            System.out.println(sb);
            return;
        }

        for (int i = start; i < target.length; i++) {
            int currentLength = sb.length();
            sb.append(target[i] + " ");
            combinationRepetition(target, i, R, count + 1, sb); // 현재를 포함한 위치부터 살핌
            sb.setLength(currentLength);
        }
    }

}

부분집합 - 주어진 원소르 만들 수 있는 모든 경우의 수

import java.util.Scanner;

public class PowerSet {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt(); // 원소 개수

        String[] target = new String[N];
        for (int i = 0; i < target.length; i++) {
            target[i] = scanner.next();
        }

        powerSet(target, 0, new StringBuilder());
    }

    // 부분집합
    private static <T> void powerSet(T[] target, int start, StringBuilder sb) {
        if (start == target.length) {
            System.out.println(sb);
            return;
        }

        int currentLength = sb.length();
        sb.append(target[start] + " ");
        powerSet(target, start + 1, sb); // 해당 수를 선택한 경우
        sb.setLength(currentLength);
        sb.append("X ");
        powerSet(target, start + 1, sb); // 해당 수를 선택하지 않은 경우
        sb.setLength(currentLength);
    }

}