[백트래킹]끝점을 늘려가면서 탐색하는 순열조합+a

#include <iostream>
#include <vector>
using namespace std;
 
struct INFO {
    bool isV = false;
};
 
INFO info[5];
int isV[5];
vector<int> v;
//EndPoint를 늘려주면서 dfs탐색
void dfs(int s,int len,int ep) {
    if (len == ep) {
        for (int i = 0; i < len; i++) {
            printf("%d ", v[i]);
        }
        printf("\n");
        return;
    }
 
    for (int i = s; i < 5; i++) {
        if (isV[i] == false) {
            isV[i] = true;
            v.push_back(i);
            dfs(i, len + 1,ep);
            isV[i] = false;
            v.pop_back();
        }
    }
}
 
int main()
{
 
    for(int i=1;i<=5;i++) dfs(0,0,i);
    return 0;
}
 

 

 

<정답을 찾은 경우 더이상 진행할 필요가 없는 경우>

#include <iostream>
#include <vector>
using namespace std;
 
int isV[5];
bool flag = false; //만약에 정답을 찾으면 재귀를 빠져나오기위한 플러그설정!
vector<int> v;
 
void dfs(int s,int len,int ep) {
    if (len == ep) {
        for (int i = 0; i < len; i++) {
            printf("%d ", v[i]);
        }
        printf("\n");
        if (len == 3) flag = true; //만약 답을 찾은경우. 뒤에꺼를 실행안되게 하기위해서.
        return;
    }
 
    for (int i = s; i < 5; i++) {
        if (isV[i] == false && flag==false) { //플러그가 true로바뀌면 실행안되도록.
            isV[i] = true;
            v.push_back(i);
            dfs(i, len + 1,ep);
            isV[i] = false;
            v.pop_back();
        }
    }
}
 
int main()
{
 
    for(int i=1;i<=5;i++) if(flag==false) dfs(0,0,i);
    return 0;
}
 

 

<X이상 이면 실행중지의 조건을 통해 Backtracking을 통한 모든 경우탐색>

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
 
vector<int> v;
bool isV[6];
 
 
void dfs(int len) {
    for (int i = 0; i < v.size(); i++) {
        printf("%d ", v[i]);
    }printf("\n");
    
    if (len == 3)return;
 
    for (int i = 0; i < 6; i++) {
        if (!isV[i]) {
            isV[i] = true;
            v.push_back(i);
            dfs(len + 1);
            v.pop_back();
            isV[i] = false;
        }
    }
}
 
int main()
{
    dfs(0);
    return 0;
}