c++ - C++ 回溯排列

Question

我正在尝试打印集合 {1, 2, ...N} 的所有排列，但没有成功。我试图通过回溯来实现它。当我向排列添加一个元素时，我检查它是否不存在，然后检查它是否是一个解决方案（如果排列中有 N 个数字），然后打印它。我正在寻找是否有人可以帮助我指出代码中的缺陷。

#include<iostream>
#include<cstdlib>
#define MAX 9
using namespace std;

int check(int *s, int N) { //checking if the elements of the permutation are all distinct
    for (int i = 1; i <= N - 1; i++)
        for (int j = i + 1; j <= N; j++)
            if (s[i] == s[j])
                return 0;
    return 1;
}

int solution(int *s, int k, int N) { //if we have reached N numbers it's a solution
    if (k == N)
        return 1;
    return 0;
}

void print_solution(int *s, int N) { //print the permutation
    for (int i = 1; i <= N; i++)
        cout << s[i] << " ";
    cout << endl;
}

void permutation_bkt(int *s, int k, int N) { //backtracking permutations
    for (int i = 1; i <= N; i++) {
        s[k] = i;
        if (check(s, N)) {
            if (solution(s, k, N)) {
                print_solution(s, N);
            }
            else {
                permutation_bkt(s, k++, N);
            }
        }
    }
}

int main() {
    int s[MAX], k = 1;
    int N; cout << "N= "; cin >> N;
    permutation_bkt(s, k, N);
    system("Pause");
    return 0;
}

标签： c++permutationbacktracking

Answer 1

基于@Jarod42，这是我尝试过的。

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

void print(vector<int>& vec)
{
    do {
        for(auto ele:vec){
           std::cout << ele << " ";
        }
        cout <<endl;
    } while(std::next_permutation(vec.begin(), vec.end()));
}

int main()
{
    vector<int> inputs{1,2,3}; 
    vector<int> vec;
    for(int i= 1;i<=inputs.size();i++){ 

        for(int j=0;j<i;j++){
            vec.push_back(inputs[j]);
        }

        print(vec);
        vec.clear();
        cout <<endl<<endl;
    }
}

输出：