[알고리즘] 순열, 조합, 중복순열, 중복조합

[yeoseon]

개요

순열

조합

• DFS의 주요 유형 중 하나
• 순열 중에서도 중복, 순서가 없는 경우의 수 구하기
• 백트래킹 또는 재귀함수를 이용한다.
• 뽑거나.. 뽑지 않거나..

풀이 1: 백트래킹 이용

https://github.com/yeoseon/tip-archive/issues/251 참고

// 백트래킹 사용
// 사용 예시 : combination(arr, visited, 0, n, r)
static void combination(int[] arr, boolean[] visited, int start, int n, int r) {
    if(r == 0) {
        print(arr, visited, n);
        return;
    } 

    for(int i=start; i<n; i++) {
        visited[i] = true;
        combination(arr, visited, i + 1, n, r - 1);
        visited[i] = false;
    }
}

풀이 2: 재귀 이용

// 재귀 사용
// 사용 예시 : comb(arr, visited, 0, n, r)
static void comb(int[] arr, boolean[] visited, int depth, int n, int r) {
    if (r == 0) {
        print(arr, visited, n);
        return;
    }

    if (depth == n) {
        return;
    }

    visited[depth] = true;
    comb(arr, visited, depth + 1, n, r - 1);

    visited[depth] = false;
    comb(arr, visited, depth + 1, n, r);
}

Reference

• 조합 구현 - 두가지 방법 모두
• 조합 구현 2 - 재귀 이용(더 자세)