백준 15663 N과 M (9)

https://hae-ong.tistory.com/88

백준 15657 N과 M (8)

15657번 문제와 달리 수를 중복 선택해서는 안되는 문제였다. 중복선택도 안되고 중복 수열도 안되기때문에 관련 조건을 2개 넣어주었다.
중복선택이 안되는 부분은 visited라는 배열로 체크해주었고, 중복수열이 안되는 부분은 prev != arr[i]로 바로 전 수열의 맨 끝자리숫자가 현재 들어갈 예정인 숫자와 동일한지 체크해주었다. 

 

중복수열을 제거하는 방법으로 끝자리를 검사하지않고 그냥 모든 중복수열을 포함해 set컨테이너에 집어넣는 방법도 좋을것같다

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, m;
int arr[9];
int ans[9];
int visited[9];



void func(int cnt){
    if(cnt == m) {
        for(int i=0; i<m; i++){
            cout << ans[i] << " ";
        }
        cout << endl;
        return;
    }
    int prev =0;
    for(int i = 0; i < n;i++){
        if(visited[i]==0 && prev != arr[i]){
            
            visited[i] = 1;
            ans[cnt] = arr[i];
            prev = ans[cnt];
            func(cnt+1);
            visited[i] = 0;
        }
        
    }
    
  
}
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
   
    for(int i=0; i<n; i++) {
        cin >> arr[i];
    }
    sort(arr,arr+n);
    func(0);
   

    return 0;
}