백트래킹(BackTracking) 경우의 수 나열

1.

중복을 허용한 모든 경우의 수.

16번 째 줄의 i = 0으로 재귀적인 함수에서도 무조건 실행되고 있다.

재귀적으로 넘겨질 때 마다, 출발은 무조건 i = 0.

#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> v = { 1, 2, 3};
 
void backtracking(vector<int> vc)
{
    if (vc.size() == 3)
    {
        printf("\n");
        for (auto i : vc) printf("%d ", i);        
        return;
    }
 
    for (int i = 0; i < v.size(); i++)
    {
        vc.push_back(v.at(i));
 
        backtracking(vc);
 
        vc.pop_back();
    }
}
 
int main(void)
{
    vector<int> vc;
 
    backtracking(vc);
 
    printf("\n");
 
    return 0;
}

1 1 1
1 1 2
1 1 3
1 2 1
1 2 2
1 2 3
1 3 1
1 3 2
1 3 3
2 1 1
2 1 2
2 1 3
2 2 1
2 2 2
2 2 3
2 3 1
2 3 2
2 3 3
3 1 1
3 1 2
3 1 3
3 2 1
3 2 2
3 2 3
3 3 1
3 3 2
3 3 3

2. 

중복을 허용한 경우의 수, 오름차순.

16번 째 줄의 i = pos와 20번 째 줄의 i를 잘보자.

i = pos인데, 20번 째 줄의 backtracking함수로 i(=pos)가 그대로 넘겨지고 있다.

그래서 중복 허용이다. 게다가 전에 했던 인덱스들은 거치지 않으므로(pos 자신부터 시작),

전의 값들은 나오지 않는다.

#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> v = { 1, 2, 3};
 
void backtracking(vector<int> vc, int pos)
{
    if (vc.size() == 3)
    {
        printf("\n");
        for (auto i : vc) printf("%d ", i);        
        return;
    }
 
    for (int i = pos; i < v.size(); i++)
    {
        vc.push_back(v.at(i));
 
        backtracking(vc, i);
 
        vc.pop_back();
    }
}
 
int main(void)
{
    vector<int> vc;
 
    backtracking(vc, 0);
 
    printf("\n");
 
    return 0;
}

1 1 1
1 1 2
1 1 3
1 2 2
1 2 3
1 3 3
2 2 2
2 2 3
2 3 3
3 3 3

#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> v = { 1, 2, 3, 4, 5 };
 
void backtracking(vector<int> vc, int pos)
{
    if (vc.size() == 2)
    {
        printf("\n");
        for (auto i : vc) printf("%d ", i);        
        return;
    }
 
    for (int i = pos; i < v.size(); i++)
    {
        vc.push_back(v.at(i));
 
        backtracking(vc, i);
 
        vc.pop_back();
    }
}
 
int main(void)
{
    vector<int> vc;
 
    backtracking(vc, 0);
 
    printf("\n");
 
    return 0;
}

1 1
1 2
1 3
1 4
1 5
2 2
2 3
2 4
2 5
3 3
3 4
3 5
4 4
4 5
5 5

3.

중복을 허용하지 않고, 오름차순.

#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> v = { 1, 2, 3};
 
void backtracking(vector<int> vc, int pos)
{
    if (vc.size() == 3)
    {
        printf("\n");
        for (auto i : vc) printf("%d ", i);        
        return;
    }
 
    for (int i = pos; i < v.size(); i++)
    {
        vc.push_back(v.at(i));
 
        backtracking(vc, i + 1);
 
        vc.pop_back();
    }
}
 
int main(void)
{
    vector<int> vc;
 
    backtracking(vc, 0);
 
    printf("\n");
 
    return 0;
}

1 2 3

참고로 2번에 있는 2번 째 코드와 20번 째 줄만 다르다. i vs i + 1

#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> v = { 1, 2, 3, 4, 5 };
 
void backtracking(vector<int> vc, int pos)
{
    if (vc.size() == 2)
    {
        printf("\n");
        for (auto i : vc) printf("%d ", i);        
        return;
    }
 
    for (int i = pos; i < v.size(); i++)
    {
        vc.push_back(v.at(i));
 
        backtracking(vc, i + 1);
 
        vc.pop_back();
    }
}
 
int main(void)
{
    vector<int> vc;
 
    backtracking(vc, 0);
 
    printf("\n");
 
    return 0;
}

1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

4. 

중복을 허용하지 않고, 모든 경우의 수

1번과 비교하여, 사용 여부 배열인 use만 추가하였다.

#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> v = { 1, 2, 3};
 
bool use[10] = { false, };
 
void backtracking(vector<int> vc, int pos)
{
    if (vc.size() == 3)
    {
        printf("\n");
        for (auto i : vc) printf("%d ", i);        
        return;
    }
 
    for (int i = 0; i < v.size(); i++)
    {
        if (use[i]) continue;
 
        use[i] = true;
        vc.push_back(v.at(i));
 
        backtracking(vc, i + 1);
 
        use[i] = false;
        vc.pop_back();
    }
}
 
int main(void)
{
    vector<int> vc;
 
    backtracking(vc, 0);
 
    printf("\n");
 
    return 0;
}

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

참고로 바로 위의 결과는 아래를 실행하여도 같다.

void backtracking()
{
    do
    {
        for (auto i : v) printf("%d ", i);
        printf("\n");
    } while (next_permutation(v.begin(), v.end()));
}

#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> v = { 1, 2, 3, 4, 5};
 
bool use[10] = { false, };
 
void backtracking(vector<int> vc, int pos)
{
    if (vc.size() == 2)
    {
        printf("\n");
        for (auto i : vc) printf("%d ", i);        
        return;
    }
 
    for (int i = 0; i < v.size(); i++)
    {
        if (use[i]) continue;
 
        use[i] = true;
        vc.push_back(v.at(i));
 
        backtracking(vc, i + 1);
 
        use[i] = false;
        vc.pop_back();
    }
}
 
int main(void)
{
    vector<int> vc;
 
    backtracking(vc, 0);
 
    printf("\n");
 
    return 0;
}

1 2
1 3
1 4
1 5
2 1
2 3
2 4
2 5
3 1
3 2
3 4
3 5
4 1
4 2
4 3
4 5
5 1
5 2
5 3
5 4