General All Permutations - Backtracking / Additional States

Problems
42

I get the preference to stick to the template but it just seems a little too verbose. I read some of the solutions in the comments here and feel they are not quite optimal because they are either creating a bunch of new strings (since strings are immutable) or they do an extra linear scan. I came up with this solution and it helped me better understand the backtracking approach. It keeps the memory usage low by turning the input string into a list which is used by the recursive function to swap elements to create a different permutation. The int step variable is used as an indicator of the number of letters that have been selected and so we start the for-loop from the step int instead of 0.

def permutations(letters: str) -> List[str]:
    def dfs_backtrack(step: int, perm: List[str]):
        if step == len(perm):
            result.append(''.join(perm))
        else:
            for i in range(step, len(perm)):
                perm[i], perm[step] = perm[step], perm[I]
                dfs_backtrack(step + 1, perm)
                perm[i], perm[step] = perm[step], perm[I]
    result = []
    dfs_backtrack(0, list(letters))
    return result
43

C++ solution using less memory as we can mark characters as used, rather than having more memory… Also avoids copying of the string recursively down the call chain, so can pass by reference. i.e. Using push/pop and resetting the used letters.



void pm(int idx, std::string& letters, std::string& path, std::vector<std::string>& res) {
    
    if (idx == letters.size()) {
        res.push_back(path);
        return;
    }
    
    for( int i = 0; i < letters.size(); ++i ) {
        char c = letters[i];
        if(c!='*') {
            path.push_back(c);
            letters[i]='*';
            pm(idx+1, letters, path, res);
            letters[i]=c;
            path.pop_back();
        }
    }
}

std::vector<std::string> permutations(std::string letters) {
    std::vector<std::string> res;
    std::string path;
    pm(0, letters, path, res);
    return res;
}
44

Javascript solution without used array:

function dfsHelper(n, path, res) {
if (n.length === 0) {
res.push(path.join(“”));
return;
}

for(let i=0; i<n.length; i++) {
    path.push(n[i]);
    let filtered = n.filter(element=> {
        return element !== n[i];
    })
    dfsHelper(filtered, path, res);
    path.pop();   
}

}

function permutations(letters) {
let res=;
dfsHelper(letters.split(“”), , res)
return res;
}

45

Another possible solution using a set to keep track of letters:

def permutations(letters: str) -> List[str]:
    res = []

    def dfs(path, seen=set()):
        if len(path) == len(letters):
            res.append("".join(path))
            return

        for letter in letters:
            if letter not in seen:
                path.append(letter)
                seen.add(letter)
                dfs(path, seen)
                path.pop()
                seen.discard(letter)

    dfs([])
    return res
47

There was a huge typo in my previous comment. If anyone is curious O(n*(n!)) = O((n+1)(n!)) = O((n+1)!). So we can write the time complexity is O((n+1)!).

48 
def permutations(letters: str) -> List[str]:
    rst = []
    def dfs(cur_path, visited):
        if len(cur_path) == len(letters):
            rst.append(''.join(cur_path))
            return
        for letter in letters:
            if letter in visited:
                continue
            cur_path.append(letter)
            visited.add(letter)
            dfs(cur_path, visited)
            visited.remove(cur_path.pop())
    dfs([], set())
    return rst
49

The space complexity should be O(n) isn’t it? At any time only n recursive call, used array take n, path take maximum n, why space complexity is O(n! * n)?