Uploaded December 2018 | Updated November 2026, 1 hour ago
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: Given a string, print all permutations of the string and return an array of them. No duplicates are allowed.
Whenever we work with problems like this, the fact that it is a string and that it is an array are interchangeable. We will permute an array the same way that we permute a string.
Why is this a backtracking problem? Because we are placing an item and then exploring all possibilities from there.
Whenever we have a problem that says "generate" or "compute" and it is an expression of several decision points that comprise a larger possibility set...WE HAVE BACKTRACKING.
The 3 Keys To Backtracking
Our Choice
What character we place in a "slot"
Our Constraints
None really...but at each decision point we will have fewer characters to work with because of our previous decisions.
Our Goal
Let n be the string length. Place n characters.
Complexities
Time: O(n * n!)
- There are n! permutations and it takes O(n) time to add each one to our result array
Space: O(n)
- We are not returning an array here so linear space because our recursion will go at maximum n elements deep since we make n choices of placement at maximum
- If we did store and return an array our space complexity would be O(n * n!) since we would have n! permutations and each permutation would be of length n. If we consider the returned array of all permutation strings as NOT part of space, the call stack dominates space. We are back to O(n).
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 16.3 in the fantastic book "Elements of Programming Interviews" by Adnan Aziz
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: Given a string, print all permutations of the string and return an array of them. No duplicates are allowed.
Whenever we work with problems like this, the fact that it is a string and that it is an array are interchangeable. We will permute an array the same way that we permute a string.
Why is this a backtracking problem? Because we are placing an item and then exploring all possibilities from there.
Whenever we have a problem that says "generate" or "compute" and it is an expression of several decision points that comprise a larger possibility set...WE HAVE BACKTRACKING.
The 3 Keys To Backtracking
Our Choice
What character we place in a "slot"
Our Constraints
None really...but at each decision point we will have fewer characters to work with because of our previous decisions.
Our Goal
Let n be the string length. Place n characters.
Complexities
Time: O(n * n!)
- There are n! permutations and it takes O(n) time to add each one to our result array
Space: O(n)
- We are not returning an array here so linear space because our recursion will go at maximum n elements deep since we make n choices of placement at maximum
- If we did store and return an array our space complexity would be O(n * n!) since we would have n! permutations and each permutation would be of length n. If we consider the returned array of all permutation strings as NOT part of space, the call stack dominates space. We are back to O(n).
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: youtube.com/user/tusharroy2525
GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: youtube.com/user/VSympathyV
Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 16.3 in the fantastic book "Elements of Programming Interviews" by Adnan Aziz

![Count Total Unique Binary Search Trees - The nth Catalan Number (Dynamic Programming)
Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://backtobackswe.com/pricing
πΉ Intuitive Video Explanations
π Run Code As You Learn
πΎ Save Progress
βNew Unseen Questions
π Get All Solutions
Question: Given n, how many structurally unique BSTs (binary search trees) that store values 1 ... n?
Catalan Numbers: https://en.wikipedia.org/wiki/Catalan_number
Define G(n): the number of unique BST for a sequence of length n.
G(0) = 1
G(1) = 1
For each element, we can place it and recurse on the left an right not including that number we choose to root that subtree.
Define F(i,n): the number of unique BST, where the number i is served as the root of BST (1 is less than or equal to i which is less than or equal to n).
G(n) = the summation from 1 to n of F(i, n)
When we choose an element to root a subtree from the possible elements to root there, we split the possibilities into a left and a right of the original enumeration.
Example:
n = 5 aka [1, 2, 3, 4, 5]
When evaluating F(3, 5) we will have
a left subtree with [1, 2] aka G(2)
a right subtree with [4, 5] aka G(2)
G(n) evaluates the # of unique trees we can construct from a total of n possible values, regardless of what those values are.
The Realization
We notice that F(i, n) = G(i - 1) * G(n - i)
To get F(i, n) we are considering all combinations of left tree possibilities with all of the right tree possibilities.
These exhaustive pairings between two sets of items is called a cartesian product.
Now we have a new way to express F(i, n)
F(i, n) = G(i - 1) * G(n - i)
G(n) = summation from 1 to n of G(i - 1) * G(n - i)
This now can be solved with DP via top-down recursion or bottom up.
For each G(n) up to our requested n we will solve the G(n) summation equation.
At the end we return the G(n) requested which by the end we will have an answer for.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: https://www.youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww
Tuschar Roy: https://www.youtube.com/user/tusharroy2525
GeeksForGeeks: https://www.youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ
Jarvis Johnson: https://www.youtube.com/user/VSympathyV
Success In Tech: https://www.youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw Count Total Unique Binary Search Trees - The nth Catalan Number (Dynamic Programming)](https://i.ytimg.com/vi/GgP75HAvrlY/mqdefault.jpg)








