Advertisement
Iam_Sandeep

Permutation of a string backtracking

May 13th, 2022
643
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. def permute(s):
  2.     s=list(s)
  3.     n,ans=len(s),[]
  4.     def dfs(i):
  5.         if i==n-1:
  6.             ans.append(''.join(s))
  7.             return
  8.         # we will swap indices from i+1 to n with i and do backtrack. This ensures generations of diff permutatations
  9.         #In recursion level 1 we do swapping from 0th index to  (0+1,n) indices
  10.         #in recursion level 2 we do swapping from 1st index to (1+1,n) indices
  11.         #in recursion level ith we do swaping from ith index to (i+1,n) indices
  12.         for j in range(i+1,n):
  13.             s[i],s[j]=s[j],s[i]
  14.             dfs(i+1)
  15.             s[i],s[j]=s[j],s[i]
  16.     dfs(0)
  17.     return ans
  18. permute("shpdwa")
  19.    
  20.        
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement