프로그래머스 : 구슬을 나누는 경우의 수

❔문제설명

머쓱이는 구슬을 친구들에게 나누어주려고 합니다. 구슬은 모두 다르게 생겼습니다. 머쓱이가 갖고 있는 구슬의 개수 balls와 친구들에게 나누어 줄 구슬 개수 share이 매개변수로 주어질 때, balls개의 구슬 중 share개의 구슬을 고르는 가능한 모든 경우의 수를 return 하는 solution 함수를 완성해주세요.

⚠️제한사항

1 ≤ balls ≤ 30
1 ≤ share ≤ 30
구슬을 고르는 순서는 고려하지 않습니다.
share ≤ balls

🤔아이디어

전에 팩토리얼 식을 만들었는데, 그걸 활용하면 안되려나

❌틀린코드

class Solution {
    
    public static int factorial(int num){ //팩토리얼 메소드
        if(num==1) return 1; 
        return num * factorial(num - 1); 
    }
    
    public int solution(int balls, int share) {
        int answer = factorial(balls) / (factorial(balls-share) * factorial(share));
        return answer;
    }
}

🙄오류

코드 실행은 되는데.. 정확도가 엉망이다.. 뭐지.. 재귀함수써서 그런가?

❌틀린코드 2

class Solution {
    
    public static double factorial(double num){ //팩토리얼 메소드
        if(num==1) return 1; 
        return num * factorial(num - 1); 
    }
    
    public int solution(int balls, int share) {
        int answer = (int)(factorial(balls) / (factorial(balls-share) * factorial(share)));
        return answer;
    }
}

🙄오류2

처음보다는 정확도가 올랐다.. 숫자의 크기가 너무커서 그런가 싶어 long로도 바꿔봤는데 도리어 정확성이 떨어졌다...

💡코드풀이

class Solution {
    public int combination(int n, int r) {
        if (r == 0 || n == r) {
            return 1;
        } else {
            return combination(n-1, r-1) + combination(n-1, r);
        }
    }

    public int solution(int balls, int share) {
        return combination(balls, share);
    }
}

nCr을 이해해서 풀어야했다. 재귀함수를 이용해서 nC0 또는 nCn을 뽑는 경우의 수가 될때까지 돌아가게 만드는 함수...!
n개중 r을 뽑는 경우의 수는 (n=3, r=2이라 할때)
1을 뽑은 경우와, 1을 뽑지 않은경우로 나뉘는데
1을 뽑은 경우에는 2 또는 3을 뽑을수 있으므로 2C1
1을 뽑지 않은 경우에는 2 3 모두 뽑아야하므로 2C2가 된다
일반식으로 표현하면 n-1Cr-1 , n-1Cr 이 두개를 합하면 n개중 r개를 뽑는 경우의 수가 된다.