BOJ/백준 15650 N과 M (2) C++

15649번은 순열, 15650번은 조합. 순열은 이전에 봤었던 것까지 고려하는 것이지만,

조합은 현재 뽑은 원소의 이전 값들은 고려하지 않게끔 for문의 i값을 넘겨준다.

조합은 순열과 달리 중복되면 안되므로 시작점이 필요하며 이전에 건든 작은 숫자를 건들지 않기 위해 구현한다.

 

인덱스를 추가하여 넘겨주면 끝!

#include <iostream>
#define MAX 10
 
using namespace std;
 
int arr[MAX];
bool visit[MAX];
 
int N, M;
 
void dfs(int cnt, int idx) {
   if (cnt == M) {
        for (int i = 0; i < M; i++) {
            cout << arr[i] << ' ';
        }
        cout << '\n';
 
    }
 
    for (int i = idx; i <= N; i++) {
        if (!visit[i]) {
            visit[i] = true;
            arr[cnt] = i;
            dfs(cnt + 1, i + 1);
            visit[i] = false;
        }
    }
 
}
 
int main(void) {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
 
    cin >> N >> M;
 
    dfs(0,1);
 
    return 0;
}