백준 BOJ 15650 N과 M(2)

permuation - 순서가 있는 경우의 수

combination - 순서 개념이 없는 조합의 경우의 수

 

permuation, combination 구현과 차이점

- permutaion은 탐색 시 처음 원소부터 다시 탐색.  (3을 골라도 이후 재귀에서 1부터 다시 탐색)

- combination은 탐색 시 현재 원소(idx)의 이후의 idx만 탐색. (3을 골랐으면 이후 재귀에서 4,5,6.. 만 고려)

 

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

15650번: N과 M (2)

 

경우의 수는 nCr = n! / ((n-r)! * r!)) 이 된다. 

(위 문제에서 n=n , r=m)

 

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<unordered_map>
#include<map>
#include<algorithm>
#include<string>
#include<cmath>
#include<stack>
#define INF 1e9
using namespace std;
using lld = long long int;
using pii = pair<int, int>;
 
bool visited[10];
int a[10];
int n, m;
 
void solve(int dep, int idx) {
    if(dep == m) {
        
        for(int i=0; i<m; i++) {
            cout << a[i] << " ";
        }
        cout << "\n";
        
        return;
    }
    
    for(int i=idx; i<=n; i++) {
        if(visited[i]) continue;
        
        visited[i] = true;
        a[dep] = i;
        
        solve(dep+1, i);
        visited[i] = false;
        
    }
    
    return;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m;
    
    memset(visited, 0, sizeof(visited));
    
    solve(0, 1);
    
    return 0;
}