// 주사위를 3번 던져 모두 다른 수 나오는 경우의 수(던지는 순서 고려)
class Permutation {
    static int N=6, R=3;
    static int[] dice;              // 주사위 숫자
    static int[] numbers;           // 순열 경우의 수
    static boolean[] isSelected;    // 주사위 숫자 포함 여부

    public static void main(String[] args) {
        dice = new int[] {1, 2, 3, 4, 5, 6};
        numbers = new int[R];
        isSelected = new boolean[N];

        permutation(0);
    }

    private static void permutation(int depth) {
        // 기저 조건 - 순열 배열에 주사위 3번 던진만큼이 저장되면~
        if (depth == R) {
            System.out.println(Arrays.toString(numbers));
            return;
        }

        // 유도 파트 - 현재 depth에 i번째 주사위 값이 올 때 가능한 경우를 전부 확인
        for (int i=0; i<N; i++) {
            if (isSelected[i]) continue;

            numbers[depth] = dice[i];
            isSelected[i] = true;
            
            permutation(depth+1);  // 다음 depth로 이동
            isSelected[i] = false;
        }
    }
}

// 주사위를 3번 던져 나오는 모든 경우의 수(던지는 순서 고려)
class PermutationWRepetition {
    static int N=6, R=3;
    static int[] dice;              // 주사위 숫자
    static int[] numbers;           // 순열 경우의 수

    public static void main(String[] args) {
        dice = new int[] {1, 2, 3, 4, 5, 6};
        numbers = new int[R];

        permutationWRepetition(0);
    }

    private static void permutationWRepetition(int depth) {
        // 기저 조건 - 순열 배열에 주사위 3번 던진만큼이 저장되면~
        if (depth == R) {
            System.out.println(Arrays.toString(numbers));
            return;
        }

        // 유도 파트 - 현재 depth에 i번째 주사위 값이 올 때 가능한 경우를 전부 확인
        for (int i=0; i<N; i++) {
            numbers[depth] = dice[i];
            permutationWRepetition(depth+1);
        }
    }
}

// 주사위를 3번 던져 모두 다른 수 나오는 경우의 수(던지는 순서 고려 안함)
class Combination {
    static int N=6, R=3;
    static int[] dice;              // 주사위 숫자
    static int[] numbers;           // 조합 경우의 수

    public static void main(String[] args) {
        dice = new int[] {1, 2, 3, 4, 5, 6};
        numbers = new int[R];

        combination(0, 0);
    }

    private static void combination(int depth, int startIdx) {
        // 기저 조건 - 조합 배열에 주사위 3번 던진만큼이 저장되면~
        if (depth == R) {
            System.out.println(Arrays.toString(numbers));
            return;
        }

        // 유도 파트 - 순서 상관 없이 이미 뽑은 숫자를 제외하고 뽑을 수 있는 모든 경우 확인
        for (int i=startIdx; i<N; i++){
            numbers[depth] = dice[i];
            combination(depth+1, i+1);
        }
    }
}

// 주사위를 3번 던져 나오는 모든 경우의 수(던지는 순서 고려 안함)
class PermutationWRepetition {
    static int N=6, R=3;
    static int[] dice;              // 주사위 숫자
    static int[] numbers;           // 조합 경우의 수

    public static void main(String[] args) {
        dice = new int[] {1, 2, 3, 4, 5, 6};
        numbers = new int[R];

        combinationWRepetition(0, 0);
    }

    private static void combinationWRepetition(int depth, int startIdx) {
        // 기저 조건 - 조합 배열에 주사위 3번 던진만큼이 저장되면~
        if (depth == R) {
            System.out.println(Arrays.toString(numbers));
            return;
        }

        // 유도 파트 - 순서와 숫자의 중복 상관 없이 뽑을 수 있는 모든 경우 확인
        for (int i=startIdx; i<N; i++) {
            numbers[depth] = dice[i];
            combinationWRepetition(depth+1, i);
        }
    }
}

class Subset {
    static int N=5;
    static int[] numbers;            // 집합
    static boolean[] isSelected;     // 해당 원소를 부분 집합 경우의 수에 넣었는지

    public static void main(String[] args) {
        numbers = new int[] {1, 2, 3, 4, 5};
        isSelected = new boolean[N];

        generateSubset(0)
    }

    private static void generateSubset(int idx) {
        // 기저 조건 - 마지막 원소까지 부분 집합에 넣을지 말지 결정했다면~(부분 집합 완성)
        if (idx == N) {
            for (int i=0; i<N; i++) {
                System.out.print((isSelected[idx] ? numbers[idx] : "_") + " ");
            }
            System.out.println();
            return;
        }

        // 유도 파트 - 집합의 첫번째 원소부터 마지막 원소까지 넣어보고 넣지 않아봄
        // 현재 원소 부분 집합에 넣을 경우
        isSelected[idx] = true;
        generateSubset(idx+1);

        // 현재 원소 부분 집합에 넣지 않을 경우
        isSelected[idx] = false;
        generateSubset(idx+1);
    }

}