c++vectorpermutationbacktracking

All permutations c++ with vector<int> and backtracking


I'm trying generate all permutations of an vector to training backtracking technique but my code don't work for all vectors (works to size to vectors)

my code :

#include <bits/stdc++.h>

using namespace std;

void permutations(int s,vector<int> v){
    if(s>=v.size())
        return;
    if( v.size()==0)
        cout<<endl;
    cout<<v[s]<<" ";
    vector<int> k = v;

    k.erase(k.begin()+s);

    for(int i =0;i<k.size();i++)
        return permutations(i,k);

}

int main(int argc, char const *argv[])
{
    vector<int> v = {1,2,3};
    for(int i =0;i<v.size();i++){
        permutations(i,v);
        cout<<endl;
    }

    return 0;
}

I think is because when my recursive function find return they break the for but maybe I 'm wrong someone can tell my what's the problem and how can I correct it please.


Solution

  • The simple way is to use standard algorithm: std::next_permutation

    void print(const std::vector<int>& v)
    {
        for (int e : v) {
            std::cout << " " << e;
        }
        std::cout << std::endl;
    }
    
    int main()
    {
        std::vector<int> v = {1,2,3};
        // vector should be sorted at the beginning.
    
        do {
            print(v);
        } while (std::next_permutation(v.begin(), v.end()));
    }
    

    Live Demo