[c++] N과 M(1~12) 유형별 정리, 백트래킹, DFS, 재귀

1. 중복 선택 제외시 : check 필요(사용했다는 것을 기록)
2. 오름차순/비내림차순 : 재귀 반복시 시작 범위 지정 필요 i=k  //k=상태 번호
3. 중복 선택 포함시 : check 필요 없음
4. 중복 선택 + 오름차순/비내림차순 : 재귀 반복시 시작 범위 지정 필요 i=st
   int st = 0;
   if (k != 0) st = arr[k-1]; // 비내림차순일 경우
   // if (k != 0) st = arr[k-1] + 1; // 오름차순일 경우
5. 수열 숫자들이 주어질 시에 : sort(arr, arr+N)으로 정렬 후 수행해야 한다.
6. 수열 숫자들에서 중복된 수가 존재시 : ex) 9 5 9 7 // 정렬 후 각 상태에서 tmp로 이전 값을 저장한 후, 다음 값 선택시 비교해서 동일하면 제외하도록 해야 한다. 

아래는 1~12 유형의 문제와 코드 및 정답을 보여줌. 

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

 

1) 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

 

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

 

3) 1부터 N까지 자연수 중에서 M개를 고른 수열
    같은 수를 여러 번 골라도 된다.

 

4) 1부터 N까지 자연수 중에서 M개를 고른 수열
    같은 수를 여러 번 골라도 된다.
    고른 수열은 비내림차순이어야 한다.

 

5) 이제부터 입력 수들이 주어짐
    N개의 자연수 중에서 M개를 고른 수열

 

6) N개의 자연수 중에서 M개를 고른 수열
    고른 수열은 오름차순이어야 한다.

 

7) N개의 자연수 중에서 M개를 고른 수열
    같은 수를 여러 번 골라도 된다.

 

8) N개의 자연수 중에서 M개를 고른 수열
    같은 수를 여러 번 골라도 된다.
    고른 수열은 비내림차순이어야 한다

 

9) N개의 자연수 중에서 M개를 고른 수열
    입력 수들 중에 중복이 있다

 

10) N개의 자연수 중에서 M개를 고른 수열
     고른 수열은 비내림차순이어야 한다.
     입력 수들 중에 중복이 있다.

 

11) N개의 자연수 중에서 M개를 고른 수열
     같은 수를 여러 번 골라도 된다.
     입력 수들 중에 중복이 있다.

 

12) N개의 자연수 중에서 M개를 고른 수열
    같은 수를 여러 번 골라도 된다.
    고른 수열은 비내림차순이어야 한다.
    입력 수들 중에 중복이 있다.