# Backtracking

Given a string , print different permutations of the string

**Points to remember :**

- If we are going through all the permutations , it is going to take O(n!) time excluding all the other processing time

**In place approach :**

We keep lock the left side of the string and keep swapping the right parts.

Complexity =O(n! * n) (assuming the time to print is O(1) ) else it is O(n! *n) (where the extra O(n) is to print the permutation)

**Using extra memory :**

Complexity =O(n! * n) (assuming the time to print is O(1) ) else it is O(n! *n +O(n!*n) ie. the time create the new string (each erase operation is O(n) )+ time taken to print each of the permutation.

**Backtracking Complexity example** — https://www.geeksforgeeks.org/rat-in-a-maze-backtracking-2/?ref=lbp