어떤 문제인가

백트래킹 문제. 15649번의 변형.

15649번과의 비교

#include <stdio.h>

char v[9]= {0};
int M,N,P[9]={0};

void b(int c) {
    int i=1,j;
    if(c==M+1) {
        for(;i<=M;i++) printf("%d ",P[i]);
        printf("\n");
        return;
    }
    
    for(j=1;j<=N;j++) {
        if(P[c-1]<j&&!v[j]) {
            v[j]=1;
            P[c]=j;
            b(c+1);
            v[j]=0;
        }
    }
}

int main() {
    scanf("%d%d",&N,&M);
    b(1);
}

딱 한 부분만 바뀌었다.

if(P[c-1]<j && !v[j])

다른 사람들의 풀이

오름차순이라는 조건에 맞춰 코드를 더 줄일 수 있었다.

#include <stdio.h>

int n,m,arr[10];
void solve(int num, int cnt){
  if(cnt==m){
    for (int i=0; i<m; i++){
      printf("%d ",arr[i]);
    }
    printf("\n");
    return;
  }

  for(int i=num+1; i<=n; i++){
    arr[cnt]=i;
    solve(i,cnt+1);
  }
}
int main(){
  scanf("%d %d",&n,&m);
  solve(0,0);
}

shirun01님의 소스
-> https://www.acmicpc.net/source/22006956

구조에 대한 고찰

1. 기본 조건(탐색이 끝날 지점)
2. 탐색을 진행하는 부분