중복 순열 (재귀, 백트래킹)

https://yabmoons.tistory.com/123?category=838490

[ 순열과 조합 구현 ] 재귀를 통한 구현(4 - 중복순열) (C++)

1 2 3에서 2개를 뽑는경우

순열: 1 2, 1 3, 2 1, 2 3, 3 1, 3 2

중복 순열: 1 1, 1 2, 1 3, 2 1, 2 2, 2 3, 3 1, 3 2, 3 3

#include <bits/stdc++.h>
using namespace std;
 
int n, m, a[10], s[10];
 
void solve(int cnt) {
    if(cnt == m) {
        for(int i = 0; i < m; i++)
            cout << s[i] << ' ';
        cout << '\n';
        return;
    }
 
    for(int i = 0; i < n; i++) {
        s[cnt] = a[i];
        solve(cnt + 1);
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n >> m;
    for(int i = 0; i < n; i++) a[i] = i + 1;
    solve(0);
    return 0;
}
 

내 나름대로의 코드도 구현해봤다.

#include <bits/stdc++.h>
using namespace std;
 
int n, m, a[10];
 
void solve(int idx) {
    if(idx == m) {
        for(int i = 0; i < m; i++)
            cout << a[i] << ' ';
        cout << '\n';
        return;
    }
 
    for(int i = 1; i <= n; i++) {
        a[idx] = i;
        solve(idx + 1);
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n >> m;
    solve(0);
    return 0;
}