백트래킹

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘

next_permutation

• < algorithm > 헤더에 정의

• 현재 수열을 사전 순으로 생각했을 떄의 다음 수열로 만들고 true를 리턴하는 함수
• 만약 현재의 수열이 사전 순으로 생각했을 때 제일 마지막이여서 다음 수열이 존재하지 않는다면 false를 리턴

형태 : next_permutation(배열에서 순열로 만들고자 하는 구역의 시작점, 배열에서 순열로 만들고자 하는 구역의 끝점)
ex) next_permutation(arr, arr+3);
next_permutation( vector1.begin( ), vector1.end( ) )

• 순열과 조합을 가지고 노가다가 빡새지는 경우가 있음.
  백트래킹은 코드도 길어지고 실수가 생길 수도 있는데,
  이를 next_permutation 를 활용하면 깔끔하게 순열과 조합 문제를 해결가능

예시 - 1,2,3을 가지고 만들 수 있는 순열구하기

• 순열을 구하고 싶은 {1,2,3,4} 배열이 있다면,
  next_permutation 함수를 사용하면 배열의 값들이 다음 순열인 {1,2,4,3} 으로 바뀌고 함수는 true 를 리턴한다.

int a[3] = {1,2,3,4};
do{
  for(int i=0; i<4; i++){
    cout << a[i];
  cout << '\n';
}while(next_permutation(a, a+4));

벡터로도 수열 만들 수 있음

vector<int> v(4);
for(int i=0; i<4; i++){
  v[i] = i+1;
}
do{
  for(int i=0; i<4; i++){
    cout << v[i] << " ";
  }
}while(next_permtation(v.begin(), v.end());

// 실행결과
// 1 2 3 4
// 1 2 4 3
//  ...
// 4 2 3 1
// 4 3 1 2
// 4 3 2 1

예시 - 1,2,3,4 에서 숫자 2개를 순서없이 뽑는 모든 경우(조합 구하기)

• 5개에서 3개를 뽑는 조합 문제라면 배열 a를 {0,0,0,1,1}로 두면된다.

int a[4] = {0, 0, 1, 1};
do{
  for(int i=0; i<4; i++){
    if(a[i] == 0)
      cout << i+1;
    }
    cout << '\n';
  }while(next_permutation(a,a+4));