✅ 1️⃣ 순열 (Permutation) — 중복 ❌

📘 백트래킹 구현

#include <bits/stdc++.h>
using namespace std;

int n = 3;
int arr[3] = {1, 2, 3};
bool used[3];
vector<int> result;

void perm() {
    if (result.size() == n) {
        for (int x : result) cout << x << " ";
        cout << "\\n";
        return;
    }

    for (int i = 0; i < n; i++) {
        if (used[i]) continue;
        used[i] = true;
        result.push_back(arr[i]);
        perm();
        used[i] = false;
        result.pop_back();
    }
}

int main() {
    perm();
}

📘 STL (next_permutation)

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3};
    sort(v.begin(), v.end()); // 오름차순 시작

    do {
        for (int x : v) cout << x << " ";
        cout << "\\n";
    } while (next_permutation(v.begin(), v.end()));
}

✅ 2️⃣ 조합 (Combination) — 중복 ❌

📘 백트래킹 구현

#include <bits/stdc++.h>
using namespace std;

int n = 3, r = 2;
int arr[3] = {1, 2, 3};
vector<int> result;

void comb(int start) {
    if (result.size() == r) {
        for (int x : result) cout << x << " ";
        cout << "\\n";
        return;
    }

    for (int i = start; i < n; i++) {
        result.push_back(arr[i]);
        comb(i + 1);  // 다음 인덱스부터
        result.pop_back();
    }
}

int main() {
    comb(0);
}

📘 STL (mask + next_permutation)

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3};
    vector<int> mask(v.size(), 0);
    fill(mask.end() - 2, mask.end(), 1); // 뒤에서 2개 선택

    do {
        for (int i = 0; i < v.size(); i++) {
            if (mask[i]) cout << v[i] << " ";
        }
        cout << "\\n";
    } while (next_permutation(mask.begin(), mask.end()));
}

✅ 3️⃣ 중복 허용 순열 (Permutation with Repetition)

📘 백트래킹 구현

#include <bits/stdc++.h>
using namespace std;

int n = 3, r = 2;
int arr[3] = {1, 2, 3};
vector<int> result;

void perm_dup() {
    if (result.size() == r) {
        for (int x : result) cout << x << " ";
        cout << "\\n";
        return;
    }

    for (int i = 0; i < n; i++) {
        result.push_back(arr[i]); // 중복 허용
        perm_dup();
        result.pop_back();
    }
}

int main() {
    perm_dup();
}

📘 결과

1 1
1 2
1 3
2 1
...
3 3

✅ 4️⃣ 중복 허용 조합 (Combination with Repetition)