N개 중에 M개 뽑기

1번 알고리즘: 포함/비포함 분기 방식

public static void f(int depth, int cnt) {
    if (depth == n + 1) {
        if (cnt == m) print();
        return;
    }

    list.add(depth);
    f(depth + 1, cnt + 1);
    list.remove(list.size() - 1);

    f(depth + 1, cnt);
}

• 깊이 depth에 대해, 해당 값을 포함하거나 포함하지 않는 두 가지 분기를 수행
• 모든 부분집합을 탐색하며 cnt == m인 경우만 출력
• 시간 복잡도: O(2ⁿ)
• 공간 복잡도: O(n)
• 불필요한 분기 많음

2번 알고리즘: 조합형 DFS 방식

public static void f(int depth, int prevNum) {
    if (depth == m) {
        print();
        return;
    }

    for (int i = prevNum + 1; i <= n; i++) {
        arr[depth] = i;
        f(depth + 1, i);
    }
}

• 조합 조건을 만족하는 원소만 탐색
• depth는 현재까지 선택한 원소 수, prevNum은 마지막으로 선택한 수
• 시간 복잡도: O(nCm × m)
• 공간 복잡도: O(m)
• 불필요한 연산 없음

성능 비교 요약

항목	1번 (포함/비포함)	2번 (조합 DFS)
시간 복잡도	O(2ⁿ)	O(nCm × m)
공간 복잡도	O(n)	O(m)
불필요한 호출	있음	없음
실행 속도	느림	빠름