[백준/C] 15651 - N과 M (3)

https://www.acmicpc.net/problem/15651

같은 수를 여러 번 골라도 된다는 조건이 추가된 버전이다.

같은 수를 여러 번 골라도 되면 used 배열을 bt 함수의 파라미터로 줄 필요가 없다는거 아닌가? 라는 생각이 들어서 bt 함수에 n, m, depth, *sequence만 줬더니 성공적으로 실행되었다!

재귀함수의 작동 원리

(매우 중요) return 시 가장 최근에 호출되었던 곳으로 돌아가게 된다.

전체 코드

#include <stdio.h>

void printSequence(int *sequence, int m) {
    for (int i = 0; i < m; i++) {
        printf("%d ", sequence[i]);
    }
    printf("\n");
}

void bt(int n, int m, int depth, int *sequence) {
    if (depth == m) {
        printSequence(sequence, m);
        return;
    }

    for (int i = 1; i <= n; i++) {
        sequence[depth] = i;
        bt(n, m, depth + 1, sequence);
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    int sequence[m];
    bt(n, m, 0, sequence);
    return 0;
}

이 문제를 백트래킹 첫번째 문제로 풀었어야 했는데...!