Coders Packet

All permutations of a string in C++

By Lokesh Madhav S

The program permutations of a string accept one string and produce all the possible permutations of it using recursion and backtracking. Here the problem is approached using C++.

Finding all the permutations of a string is a simple program that is implemented using recursion and backtracking. It uses the swapping concept to produce new combinations.

Two pointers, l, and r are used, all the elements to the left of l are set, and l is swapped with all elements to the right of it. If l and r become the same, the base condition is set. After producing the combination, the swapped elements are again backtracked to their original position so new combinations from starting can be produced.

void print_permu(string a, int l, int r, set &res){
    if (l == r)                       // if base condition store result
        res.insert(a);  
        
    for (int i = l; i <= r; i++)  
    {  

        swap(a[l], a[i]);             // swap the elements    

        print_permu(a, l+1, r, res);  // swapping is passed with l so no need to pass in recursion

        swap(a[l], a[i]);             // backtrack the result to go go to same point
    }  
     
}

 

Output here: 

Download project

Reviews Report

Submitted by Lokesh Madhav S (2208loki)

Download packets of source code on Coders Packet