15650번 N과 M (2)

문제:

• 문제 링크

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력:

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력:

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

접근 방법

1. 백트래킹을 통해 가능한 수열을 만든다.
   • 수열에서 오름차순으로 출력되는데 만약 값이 앞의 값과 같거나 작으면 거른다.

코드

접기/펼치기

#include <iostream>

using namespace std;

int n, m;

int arr[10];
int visit[10];

void func(int k)
{
    if(k==m)
    {
        for(int i=1; i<=m; i++)
        {
            cout << arr[i] << ' ';
        }
        cout<< "\n";
        return;
    }
    for(int i = 1; i<=n;i++){
    if(visit[i])continue;
    if(k>0 && arr[k] >= i )continue;
    arr[k+1] = i;
    visit[1] =1;
    func(k+1);

    visit[i] = 0;
    }

}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;

    func(0);

}

• 백트래킹에 대해 알아가는중