조합이란 n개의 숫자 중에서, r 개의 수를 순서 없이 뽑는 경우를 말한다.
조합은, 하나의 원소를 선택 할 경우 + 하나의 원소를 선택하지 않을 경우 이 둘의 합을 나타낸다.
👉사과가 5개 있고, 각 사과의 번호가 1,2,3,4,5 일 때 3개의 사과 뽑기
3번 사과를 반드시 뽑는 경우 =4C2
(3번은 정해져 있으므로, 1,2,4,5 중 2개 뽑기)
3번 사과를 뽑지 않는 경우 =4C3
(3번은 안뽑을거니까, 1,2,4,5 중 3개 뽑기)
두 경우를 합하면 결국 사과를 3개 뽑는 모든 경우의 수5C3
이 됨
public static void main(String[] args){
System.out.println(combination(3,2)); //3개 중 2개를 뽑는 조합의 경우의 수
}
public static int combination(int n, int r){
if(n == r || r == 0)
return 1;
else
return combination(n-1, r-1) + combination(n-1, r);
}
arr
: 조합을 뽑아낼 배열r
: 조합의 길이 (뽑을 개수)visited
: 조합에 뽑혔는지를 확인하기 위한 배열순열과 달리 조합은 r을 유지할 필요가 없으므로, 숫자를 하나씩 뽑을 때마다 하나씩 줄여줌
r == 0일 때 : r개의 숫자를 뽑았을 때
start
: 기준
start
를 기준으로 start
보다 작으면 뽑을 후보에서 제외, start
보다 크면 뽑을 후보