All String Permutations - Backtracking Method - JavaScript Solution

In this article we will solve the all string permutation problem with javascript by backtracking method. We will generate the solution tree and write the code accordingly,

Solution Tree

Code

class Solution {
    solve(s, op, ans){
        if(s.length===0){
            ans.add(op)
            return
        }
        for(let i=0; i<s.length; i++){
            let newIp = s.substring(0,i) + s.substring(i+1, s.length)
            op = op + s[i]
            this.solve(newIp, op, ans)
            ///backtrack
            op = op.slice(0, op.length-1)
        }
    }
    findPermutation(s) {
        // code here
        let ans = new Set()
        let op = ""
        this.solve(s, op, ans)
        let ansArr =  Array.from(ans)
        return ansArr
    }
}

Time Complexity

For a string of length n:

At each level:

• First level → n choices

• Second level → n-1 choices

• Third level → n-2 choices

• ...

• Last level → 1 choice

So total permutations:

n × (n-1) × (n-2) × ... × 1 = n!

Number of recursive calls ≈ n!

But there’s more 👇

At each leaf node:

• We are building a string of length n

• That takes O(n) time

So total time:

n! × n

Final Time Complexity:

👉 O(n × n!)

---

Space Complexity

We analyze two parts:

---

Recursion Stack

Maximum depth of recursion = n

So stack space =

👉 O(n)

---

Storing All Permutations

We store n! permutations.

Each permutation is length n.

So memory used =

n! × n

👉 O(n × n!)

---

Final Space Complexity:

Type	Complexity
Recursion Stack	O(n)
Output Storage	O(n × n!)
Total	O(n × n!)