조합과 중복조합

조합

cnt가 M(총 뽑아야 하는 개수)과 동일하면 끝난다.

start+1부터 N(뽑을 수 있는 수의 개수)까지 중복체크 없이 돈다. 이미 start+1부터 시작했기 때문이다. 

다음 조합을 위해 start+1값부터 N까지 넣어서 재귀 호출한다.

private static void findC(int cnt, int start) {
    if(cnt==M) {
        for(int i=0;i<M;i++){
            sb.append(numbers[i]).append(" ");
        }
        sb.append("\n");
        return;
    }

    for(int i=start+1;i<=N;i++){
        numbers[cnt] = i;
        findC(cnt+1,i);
    }
}

 

중복 조합

start+1부터 N(뽑을 수 있는 수의 개수)까지 중에서 조합 저장 배열의 순서(cnt)에 숫자를 저장한다.

다시 재귀로 다음 조합을 위해 start부터 N-1까지 넣어서 재귀 호출한다.

private static void findC(int cnt, int start) {
    if(cnt==M) {
        for(int i=0;i<M;i++){
            sb.append(numbers[i]).append(" ");
        }
        sb.append("\n");
        return;
    }

    for(int i=start+1;i<=N;i++){
        numbers[cnt] = i;
        findC(cnt+1,i-1);
    }
}

 

관련 문제

15650번: N과 M (2)

 

15652번: N과 M (4)