순열, 조합, 부분 집합

순열

package basic.perm;

import java.lang.reflect.Array;
import java.util.Arrays;

// 순열
public class Perm_Basic {
    static int[] src = {1,2,3,4,5};
    static int[] tgt = new int[3]; // 재귀 호출이 항상 default
    static boolean[] select = new boolean[src.length]; // 이전 자리에 사용한 src
    public static void main(String[] args) {
        perm(0);
    }

    static void perm(int tgtIdx){ // tgtIdx - 채우고자 하는 tat 배열의 index
        if(tgtIdx == tgt.length) {
            // 순열 완성
            System.out.println(Arrays.toString(tgt));
            return;
        }

        for(int i=0;i<src.length;i++){
            if(select[i]) continue;

            tgt[tgtIdx] = src[i];
            select[i] = true;
            perm(tgtIdx+1);
            select[i] = false; // next src[i]를 위해
        }

    }
}

조합

package basic.comb;

import java.util.Arrays;

public class Comb_Basic {
    static int[] src = {1,2,3,4,5};
    static int[] tgt = new int[3];
    public static void main(String[] args) {
        comb(0,0);
    }

    static void comb(int srcIdx, int tgtIdx){
        if(tgtIdx == tgt.length){
            System.out.println(Arrays.toString(tgt));
            return;
        }

        if(srcIdx == src.length) return;
        // select
        tgt[tgtIdx] = src[srcIdx];
        comb(srcIdx+1, tgtIdx+1);
        // no select
//        tgt[tgtIdx] = 0; //배열에서는 필요 x
        comb(srcIdx+1, tgtIdx);
    }
}

가장 많이 사용됨

부분 집합

package basic.subset;

// 부분 집합
// tgt가 고정이 아님
// 각 항목에 대해 고를지 말지 선택 여부가 있음 => 2^n 경우의수가 발생
public class Subset_Basic {
    static int[] src = {1,2,3,4,5};
    static boolean[] select = new boolean[src.length];

    public static void main(String[] args) {
        subset(0);
    }

    static void subset(int srcIdx){
        if(srcIdx==src.length){
            printSubset();
            return;
        }
        
        // select
        select[srcIdx] = true;
        subset(srcIdx+1);

        // no select
        select[srcIdx] = false;
        subset(srcIdx+1);
    }

    static void printSubset(){
        StringBuilder sb = new StringBuilder();
        sb.append("{");

        for(int i=0;i< select.length;i++){
            if(select[i]) sb.append(src[i]).append(" ");
        }

        sb.append("}");
        System.out.println(sb);
    }
}

순열 : https://www.acmicpc.net/problem/15649

조합 : https://www.acmicpc.net/problem/1010

부분집합 : https://www.acmicpc.net/problem/2961