순열과 중복순열

순열

중복을 제거하기 때문에 flag가 필요하다. cnt가 M(총 뽑아야 하는 개수)과 동일하면 끝낸다.

0부터 N(뽑을 수 있는 수의 개수)까지 중에서 이미 뽑은 수를 제외하고 해당 순서에 숫자를 저장한다.(순열 저장 배열)

다시 재귀로 다음 순서부터 순열을 찾는다.

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

    for(int i=0;i<N;i++){
        if((flag&1<<i) != 0) continue;
        numbers[cnt] = i+1;
        findP(cnt+1,flag|1<<i);
    }
}

 

중복순열

0부터 N(뽑을 수 있는 수의 개수)까지 중에서 중복 상관없이 순열 저장 배열의 해당 순서에 숫자를 저장한다. 

다시 재귀로 다음 순서부터 순열을 찾는다.

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

    for(int i=0;i<N;i++){
        numbers[cnt] = i+1;
        findP(cnt+1);
    }
}

 

관련 문제

15649번: N과 M (1)

 

15651번: N과 M (3)