All Valid Subsets & Permutation & Parentheses
There are some questions will require you to list all possible subsets of certain characters, or all permutations of some random number. It seems very hard to deal with it when the characters or numbers are in a large scale. For example if let you find all subsets of "ABC", the answer set will only contain 2^3 = 8 elements. However if it become "ABCDEFGHIG" , then we will have 2^10 = 1024 elements in our result set, which is almost impossible to do it manually. That is why this kind of question become very interesting. As a software engineer, we need be able to let computer to do this tedious work for us and it will do it quick & without any mistake. Besides, more importantly, after we write some recursive code, we need to understand how the recursive tree will look like. It is , indeed, a part of the charming of programming.
-- All Subsets 1
Given a set of characters represented by a String, return a list containing all subsets of the characters.
Assumptions
- There are no duplicate characters in the original set.
Examples
- Set = "abc", all the subsets are [“”, “a”, “ab”, “abc”, “ac”, “b”, “bc”, “c”]
- Set = "", all the subsets are [""]
- Set = null, all the subsets are []
---------------------------------------------------------------------------------------------------------------------
We could use backtrack algorithm( we actually discussed this algorithm before ) to solve this easily.
Here is a solution in JAVA:
Note, if this backing code is somewhat mysterious to you, then you may want to use pen and paper to draw some call stacks of a simple example like "abc", which will help you to understand what is going on under the hood. ( Here some call stacks I traced )
1. Base case determines recursive tree's height
2. # of times it call itself in the method body determines the branch factor
-- All Subsets 2
How about a almost identical problem with possible duplication of letters ?
Given a set of characters represented by a String, return a list containing all subsets of the characters.
Assumptions
- There could be duplicate characters in the original set.
Examples
- Set = "abc", all the subsets are ["", "a", "ab", "abc", "ac", "b", "bc", "c"]
- Set = "abb", all the subsets are ["", "a", "ab", "abb", "b", "bb"]
- Set = "", all the subsets are [""]
- Set = null, all the subsets are []
------------------------------------------------------------------------------------------------------------------------
Well since it is almost identical to the subsets 1, except it may contains some duplicate letters, so only thing we need to add into the solution of the first one is de-duplication steps.
We added line 9 --> Let same character be in adjacent positions
line 22 --> After add this character into final solution we skip all the possible duplications
-- All Permutation 1
Given a string with no duplicate characters, return a list with all permutations of the characters.
Examples
- Set = “abc”, all permutations are [“abc”, “acb”, “bac”, “bca”, “cab”, “cba”]
- Set = "", all permutations are [""]
- Set = null, all permutations are []
-----------------------------------------------------------------------------------------------------------------
Do you feel that all permutation problem is somewhat related to the all subsets problem ?
Actually are related and we will use the same approach trying to solve it, but remember for all subsets problem we have 2^N cases, which means for any random letter we either add into final solution, or not.
However, for all permutation problem we will have N * (N-1) * (N-2)* ... *1 = N! cases.
Here is a working solution in JAVA:
Notes: the for loop from 17 - 20 was full of mysterious to me at the beginning
What it will do is start from a position and swap every upcoming position with this one.
Here are some call stacks.
--All Permutation 2
So what we gonna do when there are some duplicate letters -_- ?
Again we need to de-duplication and the way we do is to keep a set for every branch, and do not swap with a upcoming letter if we already meat it before ( swap two same letter will make no difference in the result ).
Line 16 and 18 will do the de-duplication job.
-- All Parentheses 1
Given N pairs of parentheses “()”, return a list with all the valid permutations.
Assumptions
- N >= 0
Examples
- N = 1, all valid permutations are ["()"]
- N = 3, all valid permutations are ["((()))", "(()())", "(())()", "()(())", "()()()"]
- N = 0, all valid permutations are [""]
You actually can consider this question as follows: suppose you have k parentheses to use, which means the string length will be 2k ( k left paren + k right paren ). Then suppose you have a 2k length char array, for every position you may have 2 choose : either put '(' or ')'. But wait a second, do we really have 2 choose for every position ? Definitely not, for example the very first position can not put a ')'. So that is a important point that this question need to consider.
As you can see from the comment, when considering what to add at current position(index)
there are 2 possible cases
1. if we still have left paren left, then we could add left paren
2. if left paren is used more then right paren then we could add right paren at this position.
if we consider how this recursive tree will look like , First, we will have a 6 level tree ( height is determined by the base case), and for each level, if not considering cutting any branch out, will have 2 branches. Therefore, Time complexity --> O(2^6) , Space Complexity --> O(6)
There will be another blog concerning the understanding the recursive tree coming, I hope we all enjoy it.
Happy Coding :-)
Ye Jiang
No comments:
Post a Comment