# General All Permutations - Backtracking / Additional States

Actually we dont need to use extra array to check whether a letter is used or not:

def permutations(l):
# WRITE YOUR BRILLIANT CODE HERE
if not l:
return []
res = []
permutation = []

``````def dfs(l, permutation, res):
if len(permutation) == len(l):
res.append(list(permutation))
return

for letter in l:
if letter not in permutation:
permutation.append(letter)
dfs(l, permutation, res)
permutation.pop()

dfs(l, permutation, res)
return res
``````

if letter not in permutation: âŚ this line would be a problem when there are duplicate characters in âlâ

but checking if a letter in current permutation cost O(n) time, while checking a âusedâ flag is O(1)

@konnomiya - you are incurring a heavy cost of searching in an array (OlogN at best) when you do âif letter not in permutationâ. by keeping a set or a bitmap like the solution here it becomes O(1). actually there is a way to not have any state check - by swapping the elements in the input. check the LC solution: https://leetcode.com/problems/permutations/solution/

Compare âGet Itemâ to âx in sâ for list operations here: https://wiki.python.org/moin/TimeComplexity . Doing this will increase the time complexity of our code by adding this linear time execution inside an inner loop.

Hi mod, for the Python solution. The code outputs the right answer, just the formatting doesnât match the expected output.

The comment on line 9 may need to be updated. Isnât res appending a String not a List?

What is the Space Complexity of this solution?

The pass criteria could be updated to accept results emitted in a different order (see solution above).

The following code does the same thing but much more cleaner:

def permutations(letters: str) â List[str]:
res = []
def perm(let, cur_res):
nonlocal res
if len(let) == 0:
res.append(cur_res)
for i in range(len(let)):
perm(let[:i] + let[i+1:], cur_res + let[i])

``````perm(letters, "")
return res
``````

Note that the solution currently expects the results to be sorted. I had to sort the list I created:

``````from typing import List

def permutations(letters: str) -> List[str]:
# WRITE YOUR BRILLIANT CODE HERE
results = set()

def backtrack(listed, startIndex):
if startIndex == len(letters):
return

for char in range(1, len(listed)):
listed[0], listed[char] = listed[char], listed[0]
backtrack(listed, startIndex + 1)
listed[char], listed[0]  = listed[0], listed[char]

# swap letters

backtrack(list(letters), 0)
return sorted(list(results))

if __name__ == '__main__':
letters = input()
res = permutations(letters)
for line in res:
print(line)
``````

``````public static List<string> Permutations(string letters)
{

var res = new List<string>();
_permutations(letters, new System.Text.StringBuilder(letters.Length), 0, res);
return res;
}

public static void _permutations(string str, System.Text.StringBuilder prefix, int usedMask, List<string> res){

if (prefix.Length == str.Length){
return;
}

for (int i=0; i<str.Length; i++){

//Check if this bit is on for this index
if ( (usedMask & (1 << i) ) > 0 ){ continue; }

//Store the permutation so far (until it gets to max size and the next dfs will backtrack after storing it)
prefix.Append(str[i]);

//Turn on bit for index i for next dfs call so we don't process this letter again
//Use a new mask so we don't change the one associated with this current stack frame

//Down we go

//Pull the last letter off now that we ran all the permutations with it ending the prefix sequence
prefix.Remove(prefix.Length-1,1);
}
}
``````

/C++ Version/

void BuildTree(std::string letters, std::string path, std::vectorstd::string& stringVec)
{
for(int i = 0; i < letters.length(); ++i)
{
//Store letter for use in path
char aLetter = letters[i];

``````    //Remove letter since used as part of the permutation
std::string lettersCopy = letters;
lettersCopy.erase(i,1);

if(lettersCopy.length() > 0)
{
BuildTree(lettersCopy, path + aLetter, stringVec);
}
else
{
stringVec.push_back(path + aLetter);
}
}
``````

}

std::vectorstd::string permutations(std::string letters) {

``````std::vector<std::string> stringVec;

BuildTree(letters, "", stringVec);

return stringVec;
``````

}

Weird format fix:

//Store letter for use in path
char aLetter = letters[i];

Still weird formatting: fixing againâŚ

char aLetter = letters[i]; //Store letter for use in path

Why does order matter in the tests?

Very clear explanation, I did some backtracking problems before, never realized it actually has a pattern. Thanks for summarizing.

Quick question I did it on a diferent compiler and it worck but when I try it here its not giving me the right answer

from typing import List

def permutations(letters: str) â List[str]:
listL=[]
bfs(letters.split(),listL,ââ)
return listL

def bfs(letters,listL,s):
if (len(letters)==0):

``````        listL.append(s)

for x in letters:
s+=x

temp=letters[:]
temp.remove(x)
bfs(temp,listL,s)
s=""
return listL
``````