조합

조합이란

N개 중에 r개를 "순서와 무관하게" 뽑는 경우의 수

조합 경우의 수만 생각하는 경우
nCr = n-1Cr-1+n-1Cr;
1) n-1Cr-1 : 마지막 원소를 뽑은 경우
2) n-1Cr : 마지막 원소를 뽑지 않은 경우
3) r = 1일 경우 nC1 = n개
4) n = r일 경우 nCr = 1개

조합 코드(재귀)

import java.util.Arrays;

public class Combination {
    public static void main(String[] args) {
        int arr[] = {1,2,3,4,5};
        comb(0,0,new int[3],arr);
    }
    public static void comb(int cnt, int idx, int[] tmp, int[] arr)
    {
        if(idx==tmp.length)
        {
            System.out.println(Arrays.toString(tmp));
            return;
        }
        for(int i=cnt;i<arr.length;i++)
        {
            tmp[idx]=arr[i];
            comb(i+1,idx+1,tmp,arr);
        }
    }
    //재귀 다른방법2
    public static void comb2(int cnt, int idx, int[] tmp, int[] arr)
    {
        if(idx==tmp.length)
        {
            System.out.println(Arrays.toString(tmp));
            return;
        }
        if(cnt==arr.length)
        {
            return;
        }
        tmp[idx]=arr[cnt];
        comb2(cnt+1,idx+1,tmp,arr);
        comb2(cnt+1,idx,tmp,arr);
    }
}