All Permutations of a String in Python using Recursion
<p>I have this following Python code which returns a list of all the permutations of a given string using recursion. I tried my best to understand the working of the code but I am failed to do so. Can anyone please give me a breakdown of the code mentioned below?</p>

<pre><code>def permute(s):
    out = []

    # Base Case
    if len(s) == 1:
        out = [s]

    else:
       # For every letter in string
       for i, let in enumerate(s):
           for perm in permute(s[:i] + s[i+1:]):
                # Add it to output
                out += [let + perm]
    return out

permute('abc')
['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
</code></pre>

<p>If the length of the string is one, there is only on permutation, so it returns only that string in this case.</p>

<p>If there are more letters, however, it goes through every letter in the string, they are each treated as the first letter in the permutations that get added in <code>out</code> in that iteration. Then it goes through every permutation of the rest of the string, and adds each of those to <code>out</code>, with <code>let</code> being the first letter.</p>

<p>But as <code>permute('aab')</code> wouldn't yield <code>['aab', 'aba', 'baa']</code>; each entry would be in the returned list twice.</p>

<p>To avoid that, use sets instead. So <code>out = set()</code>, <code>out = {s}</code>, and <code>out.add(let + perm)</code> instead of <code>out = []</code>, <code>out = [s]</code> and <code>out.append(let + perm)</code>.</p>

python recursion data-structures permutation