[백준 15656번] N과 M (7) (C++)

문제링크 : https://www.acmicpc.net/problem/15656

15656번: N과 M (7)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int N, M;
int arr[7];
int visited[7];

void Backtracking(int n)
{
    if(n == M)
    {
        for(int i = 0; i<M; i++)
        {
            cout << arr[visited[i]] << " ";
        }
        cout <<'\n';
        return;
    }

    for(int i=0; i<N; i++)
    {
        visited[n] = i;
        Backtracking(n+1);
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> N >> M;

    for(int i=0; i<N; i++)
    {
        cin >> arr[i];
    }

    sort(arr, arr+N);

    Backtracking(0);

    return 0;
}

백트래킹 문제이다.

 

i = 0 일 때

visited[0]= 0, visited[1]=0, visited[2]=0, visited[3]=0 

-> arr[0], a[0] 출력

 

맨처음 백트래킹을 호출했을 때로 돌아감 -> visited[1] = 1로 바뀜

visited[1]=1, visited[2]=1, visited[3] =1

-> arr[0], arr[1] 출력

 

맨처음 백트래킹을 호출했을 때로 돌아감 -> visited[1] = 2로 바뀜

visited[1]=2, visited[2]=2, visited[3] =2

-> arr[0], arr[2] 출력

 

맨처음 백트래킹을 호출했을 때로 돌아감 -> visited[1] = 3로 바뀜

visited[1]=3, visited[2]=3, visited[3] =3

-> arr[0], arr[3] 출력

 

위의 과정 반복