[백트래킹]조합,순열,중복조합,중복순열

Vector를 이용하느냐의 차이에 의해서 유사해보이지만 완전히 다른 방식으로 해서 완전히 시험에 털려버렸다..ㅋ

 

<조합>

조합의 경우는 순서에 상관없이 전에 참조했던것을 참조하지 않고 선택만 하면 된다.

따라서 그냥 배열에 true표시만 해주고 1부터 N까지를 탐색하며 true를 골라주면 된다.

*내가 실수했던건, 순열에서 똑같이 구현하고 시작점만 0으로해줬다는 것이다... 이런식으로 하면

사실 true가 새겨지는 과정은 순서가 존재하지만 1부터N까지 탐색하며 true를 고르기 때문에 아무의미X..*

 

#include <iostream>
#include <vector>
using namespace std;
 
struct INFO {
    bool isV = false;
};
 
INFO info[5];
int isV[5];
vector<int> v;
 
void dfs(int s,int len) {
    if (len == 3) {
        for (int i = 0; i < 5; i++) {
            if (isV[i] == true) printf("%d ", i);
        }
        printf("\n");
        return;
    }
 //그냥 true를 표시만 해주는것..(선택)
    for (int i = s; i < 5; i++) {
        if (isV[i] == false) {
            isV[i] = true;
            dfs(i, len + 1);
            isV[i] = false;
        }
    }
}
 
int main()
{
    dfs(0,0);
    return 0;
}
 

#include <iostream>
#include <vector>
using namespace std;
 
struct INFO {
    bool isV = false;
};
 
INFO info[5];
int isV[5];
vector<int> v;
 
void dfs(int s,int len) {
    if (len == 3) {
        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);
            isV[i] = false;
            v.pop_back();
        }
    }
}
 
int main()
{
    dfs(0,0);
    return 0;
}
 

 

<중복조합>

조합을 뽑는데 중복으로 뽑을 수 있는 경우는 따져보자.

중복조합의 경우에도 true를 조합의 방식처럼 한다면 같은 수에 true를 두번 할수없기 때문에 말이 안된다.

따라서 vector를 통해서 구현해야함을 알 수있다. 방문여부를 따질 필요가 없다 중복을 허용하기 때문에.

 

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

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

 

 

<중복순열>

같은 숫자를 또 선택할수있는 중복순열의 경우 순열의 경우에서 방문여부만 제거해주면 된다.

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