Search⌘ K
AI Features
Home
Courses
Dynamic Programming in Python: Optimizing Programs for Efficiency

Solution Review: Find All Permutations of a String

Understand how to find all permutations of a string by breaking down the problem recursively and focusing on one step at a time. Learn the importance of base cases in recursion and analyze the factorial time complexity of this approach. This lesson helps you solidify foundational recursion skills essential for dynamic programming.

We'll cover the following...

Solution #

Python 3.5
def permutations(str):
  if str == "": # base case
    return [""]
  permutes = []
  for char in str:
    subpermutes = permutations(str.replace(char, "", 1))    # recursive step
    for each in subpermutes:
      permutes.append(char+each)
  return permutes
def main():
  print (permutations("abc"))
main()

Explanation

Just as we learned in previous lessons, the key to acing recursion is focusing on one step at a time. Try to think of this problem in this way: you already have every possible arrangement of every possible subsequence of the string ...