Algorithm] 조합(combination) (JAVA)

2.조합(Combination)

전체 개수 중에서 원하는 개수만 뽑는 경우의 수.


조합의 알고리즘은
arr의 idx번째를, sel에 담자. 라는게 기본 틀이다.
한번 담아보고, 한번 안담아보고를 반복하면 됨.(idx값의 변화) arr에 idx번째를 sel의 k번째에 담고,
담은걸 유효화 하려면 k를 늘려주고 k를 그대로 가져가면된다.

public class Combination{
    public static void main(String[] args) {
    
        int[] arr = {1,3,5,7,9};
        
        //선택하려는 개수
        int r = 3;
        combination(arr, new int[r], 0,0);    
    }
    
    static void combination(int[] arr, int[] sel, int idx, int k) {
        //기저조건 : 전체 개수 중에서 k개를 모두 골랐을 때.
        if(k==sel.length) {
            System.out.println(Arrays.toString(sel));
            return;
        }
 
        if(idx==arr.length)
            return;
        
        sel[k] = arr[idx];
        combination(arr, sel, idx+1, k+1);
        combination(arr, sel, idx+1, k);
    }
}