Thanks as always for watching this video guys! If there is any other interview question you'd like me to cover in the future, you can (anonymously) let me know at this link here :) -> www.csdojo.io/contribute
I have a message for anyone who sees this examples as difficult: Don't let your brain fool you. When encountering something we don't know, our brain is extremely, EXTREMELY good at convincing us that given task is either: too complicated for us, too boring for us or both. See through it. Look at the whole picture. For example. You have some skills that are easy for you now. Let's say typing on keyboard. Do you remember how hard it was in the beginning of developing that skill? And how your brain made same assumptions about what you are doing, that this is maybe stupid, or boring, and who the fuck placed those stupid keys in this non alphabetical order?. Try to remember exactly that feeling, then how you overcome it, and how it is easy for you now. Same shit here. Your brain is tricking you. It's not subject, it's just automatic reaction of our brain. See through it, persevere. It'll be hard, starting learning programming is hard, but in the end, you'll do it with fucking excitement and pleasure, I'm telling you. I was absolutely dumb at school, i didn't know what PI is in mathematics, fucking multiplying two digit numbers was my peak achievement. But. I always believed that if I'll decide firmly enough, I can learn anything, because anything can be interesting, extremely interesting, if you put enough focus and effort in it. Five years later, I'm middle Java developer of web applications. I did it, so can you.
Hi Kolos, I came in comment section to see comments where people say it helped alot, they got the concept very clearly and then hate myself that why I am not getting it, this is not my cup of tea.I was almost about to leave it... but I found your comment, now I'll again go through the video and finish it when I'll get it in my mind :)
There's a way elegant way to solve it with a binary representation of the input array. Since the elements in the array are unique they can be represented as 0 or 1 (present or NOT present). Lets say we have an array [1, 3, 5, 7]. array[0] = 1; array[1] = 3; array[2] = 5; array[3] = 7; All we need to to is to define a printing method that prints all entries where 1 is on in the binary representation of our iteration. In our example, the subsets can be represented by all the binary options from 0 to 4 (decimal, the array size) are: 0000 = {} 0001 = {1} 0010 = {3} 0011 = {1, 3} 0100 = {5} 0101 = {1, 5} 0110 = {3, 5} 0111 = {1, 3, 5} and so on, till we get to 2^n options, in our case - 2^4 = 16 permutations. 1111= {1, 3, 5 ,7}
#python solution for this approach def subsets_binary_way(array): for i in range( pow(2,len(array))): binary_array = [int(j) for j in bin(i)[2:]] zero_array = [0]*(len(array) - len(binary_array)) binary_array_full = zero_array + binary_array sub_array = [array[k]*binary_array_full[k] for k in range(len(binary_array_full))] print([i for i in sub_array if i !=0])
@@AkshayKumar-pf1qf nice one! you inspired me. here is my implementation. ``` def subsets_binary_way(array): for i in range(2 ** len(array)): bs = bin(i)[2:].zfill(len(array)) print([array[k] for k in range(len(bs)) if bs[k] == '1']) ```
I wanted to share an iterative approach that I thought about while watching this video. Consider an example where you have eight elements. The total number of possible combinations is 2^8 (256). If we were going to use a for loop in C++, your loop might look like this: for(int i = 0; i < 256; i++). If you covert the index of 'i' into binary, you can visualize this as switches that tell you which elements to print out. For example, the last combination you print out will be where 'i' is equal to 255. That can be represented in binary as 1111 1111. Each index of this binary number represents an index in your initial array and as you look through this binary number from left to right, if the index is 1 then you print out the associated value from the array.
Dear Matthew, Yes, your method is way clearer than CJ DoJo's method. But still, both CJ DoJo's and your method are inefficient. For example, CJ DoJo's method is those method circulating on the internet. But it has a few serious flaws; 1. In real applications, we do not need to construct all subjects. For example, if we are given a set of 4 elements S = { a, b, c, d}, and we usually want to construct subsets with a specific number of elements, such as two or three, but not all subjects. 2. If we are to use either your method or CJ DoJo's method, we have to iterate 2^(number of elements, in this case 4) times only to construct subsets with a specific number of elements. It's a huge waste of computing resource. 3. CJ DoJo's method is not PARALLELIZABLE. 4. CJ DoJo's method is a recursive method, which is awfully slow and inefficient. Whereas, I implemented subset constructions using nCr = n-1Cr-1 + n-1Cr equality, both using recursion and loop. Of course, the loop method is much faster. th-cam.com/video/9rZMqwW52D0/w-d-xo.html My method is parallelizeable and base on Loop. The biggest advantage of this method is that instead of enumerating all subjects with a specific number of elements, we can construct the k-th subset with r elements, where 0
This Worked for me in Python: a = int(input("Enter Range:")) ss=[] b1=[] lst=[] ss1=[] ss2=[] for t in range(a): b = int(input()) b1.append(b) b1_len = len(b1) for i in range(0,b1_len): for j in range(i+1,b1_len): lst = [b1[i],b1[j]] ss.append(lst) for t in range(0,a): ss.append(b1[t]) ss.append(ss1) print(ss)
Since we're printing out the power set of the original set, this is the shortest solution you can find for i = 0 to 2^n: print binary_representation_of(i) * original_set;
here's my solution it uses the fact that the subsets of, for eg. [3,5,7], will always be (subsets of [5,7] + [append 3 in every subset of [5,7]) (p.s. this is also a way to understand why the power set of n+1 elements is always 2 times the size of power set of n elements) The code(Python3): def get_all_subsets(s): subsets = [] if len(s) == 0: subsets.append([]) else: s_copy = s.copy() first_element = s_copy.pop(0) subsets += [x for x in get_all_subsets(s_copy)] subsets += [[first_element, *x] for x in get_all_subsets(s_copy)] return subsets print(get_all_subsets([5, 7, 8]))
Don't let your brain fool you. When encountering something we don't know, our brain is extremely, EXTREMELY good at convincing us that given task is either: too complicated for us, too boring for us or both. See through it. Look at the whole picture. For example. You have some skills that are easy for you now. Let's say typing on keyboard. Do you remember how hard it was in the beginning of developing that skill? And how your brain made same assumptions about what you are doing, that this is maybe stupid, or boring, and who the fuck placed those stupid keys in this non alphabetical order?. Try to remember exactly that feeling, then how you overcome it, and how it is easy for you now. Same shit here. Your brain is tricking you. It's not subject, it's just automatic reaction of our brain. See through it, persevere. It'll be hard, starting learning programming is hard, but in the end, you'll do it with fucking excitement and pleasure, I'm telling you. I was absolutely dumb at school, i didn't know what PI is in mathematics, fucking multiplying two digit numbers was my peak achievement. But. I always believed that if I'll decide firmly enough, I can learn anything, because anything can be interesting, extremely interesting, if you put enough focus and effort in it. Five years later, I'm middle Java developer of web applications. I did it, so can you.
I rarely give compliments bc I always have something that bothers me about the video (i don't compliment tech videos) but WOW!!!! you're exceptional. your videos are AMAZING!!!! I have a physics degree went into DS/ML like most of us do and now I'm switching to CS. Your videos are so clear cut your speech is impeccable, perfect pace, sound and visual, and a nice flow. I can tell you did multiple takes or practice (if not that's REALLY impressive). combined with all you have a great knowledge base and present it *flawlessly*. Most of my interviews were things you covered and your videos are also the right amount of time. It's short enough to maintain interest and long enough to give you thoroughly. It's kind of a shame that people will only really tune in during interviews or when they are learning CS/DS. You structured it well with depth and breadth. You go into a great overview and then have videos that go into more specific which is WAY better than having one long video. I wish I saw these videos before just doing a bunch of leetcode problems. It's a great clean organized way of explaining the tools. I didn't know how many leetcode problems were enough but this is great! I used your info so much on interviews. It's so memorable and keeps my attention (I have ADHD so I'm really picky with videos). I'll definitely share your channel with people interviewing or anyone new to coding. If you decide to leave TH-cam please keep these videos up. Also, you don't have that annoying "Aren't you amazed how smart I am?" arrogant vibe. You have a very humble, enthusiastic energy. Okay, this comment is way too long it's kind of creepy, but I'm a girl so how dangerous can I be? I just really wanted to let you know your videos are powerful and I really appreciate the time you take to edit them, it makes watching/learning so much easier. I know it's a lot of effort and it might not be obvious to people watching bc we're so focused on learning but I thought you should know it sets you apart.
Also, I actually was mainly referring to the videos about databases and algorithms. But I was on this video so iI commented here. I can copy and paste it there thought. I realized what I said might not seem as relevant as it does for the other ones I watched multiple times. (that sounds creepy but it's to really solidify the information and go back to see your code or your examples etc. it's not the whole thing.
How about this solution ? Since we know the number of subsets Represent that number in its binary form and essentially go from 0 till that number - 1. For the above example Now we start with 00 and go all the way till 11 where each position denotes the element and 1 denotes it’s included So for e.g. : [1,2] 00 : [] 01 : [2] 10 : [1] 11 : [1,2]
The thing is if you desire to print all subsets, you have to go in the array from start to end in each subset, how would you handle it?, unless a hashmap would be used. xd
Use a Map map to arrive at an iterative solution. The key stores the index for visited elements in array i,e 0,1,2...etc. The String[] stores different possible string with all previous map values. Time complexity should be O(n * log(n)). Print all the values for each key and you should have all the subsets
This was awesome! For an iterative solution, I built out a tree. When the added node had a depth == len(passed_array) I added that node to a list. The data of each node contained the full set up to that point, so at the end, I was able to iterate through each node in the list of final-sets and call print on it.
If , say you are given an eight element set: make a list of all possible 8-bit binary strings and wherever 1 occurs in the string, that is the index of the element from the set that we should include in our list , the take the union(possible to do in python) and print .
Caution: the subset array must be passed by value, otherwise, when the recursion returns at the second call to helper, the value of subset array will be different as the first call to helper overwrote it
My first thought was masking the elements of the array with a binary number. (I think someone else may have seen this solution too). The solution becomes counting to 2 to the power of elements in the array and at each step, mask the elements of the array with the binary number. 0 means dont print the element, 1 means do print it. eg for his example we're counting to 4 and masking with {0,0}, {0,1}, {1,0}, {1,1) resulting in the empty array for {0,0), {2} because the "1" element is masked out from {1,2} when you apply {0,1} to it and so on. Minimal memory needed.
There's an iterative approach that's much easier and doesn't require keeping track of any nulls. Here it is coded in python: def printAllSubsets(givenArray): subsets = [[]] print(subsets[0]) for i in givenArray: for j in range(len(subsets)): newSubset = subsets[j][:] newSubset.append(i) subsets.append(newSubset) print(newSubset) printAllSubsets([1,2])
We can also replace 2^n with (1+1+(nc1+-------+nc(n-1)) and create a function which prints null and complete set first. Then iterate the rest of the times to print subset containing (1,2,3 and so on) element in a set. U will exactly have same number of subsets of a particular combination as you want using (nc(r-1)).
It can be solved by binary coding. We use n sized binary code. The permutation of the code is 2^n. We simply iterate from 0 to 2^n-1 and for each number get the bits of the number. The binary form of this each number represents one subset. The bits of the number represents if any element of data is included in the set or not. Simply put, if i'th bit is 1 then i'th element in the input data is included in this subset and vice versa.
An iterative can solution can be traversing number from 0 to 2^n. For each number get binary bits (0 or 1). If it's 1 - print a number in the corresponding postion of given_array.
Generate all int between 0 and 2^n-1. The binary representation of the int tells if an element should be included in the subset. If bit X is set, include the number at position X. Otherwise, skip it.
Thanks for visualizing the recursion tree, it gave me an idea how to solve this, but I couldn't put it into words till I finished watching the video. I've made an iterative solution using Javascript. At each step, it makes a decision whether to add an item to current combination or not. This significantly simplified the code I was trying to write, thanks for all the tips! Code: function powerSet(inputs) { const results = []; const stack = [[[], 0]]; while(stack.length > 0) { const [combination, index] = stack.pop(); // we have reached the final index of combination, push to results and exit if (index === inputs.length) { results.push(combination); continue; } // do not add current element, make a copy of existing combination and push it to stack stack.push([[...combination], index + 1]); // add current element to combination and push it to stack combination.push(inputs[index]); stack.push([combination, index + 1]); } return results; };
Hello Mr. Dojo, I like the way you explain the algorithm. Here is my solution in java: public void printSubSet(String[] numArray) { String[] oldList = {""}; for (int i = 0; i < numArray.length; i++) { String[] ar = new String[oldList.length * 2]; for (int j = 0; j < ar.length; j++) { if (j < oldList.length) { ar[j] = oldList[j]; } else { ar[j] = oldList[j - oldList.length] + numArray[i]; } } oldList = ar; } System.out.println("Printing subset : " + Arrays.toString(oldList)); System.out.println("Number of subset : " + oldList.length); }
# One way to utilize recursion for this task in Python: def get_all_sets(elts): if elts: if len(elts) > 1: remaining = get_all_sets(elts[1:]) return [*remaining, *[[elts[0]]+r for r in remaining]] else: return [[], elts] return [[]] # Test print(get_all_sets([])) print(get_all_sets([1])) print(get_all_sets([1, 2])) print(get_all_sets([1, 2, 3])) print(get_all_sets([1, 2, 3, 4])) # I used lists as arguments for simplicity and ease of algorithm understanding.
Recursion is the key. Recursion uses the memory stack. So if we could somehow make use of the stack data structure, the problem can be solved in iterations.
Yes, I don't think there can be any other way, as there is only top-down approach available for this problem but not the bottom-up. So it should be done using a stack. Did you try it out?
I simple iterative approach would be to iterate from 0 to 2^n and for each num check if any bit is set among ciel(log(x)) bits , for each set bit print the element . This way you will get a subset for each x.
Iterative solution I came up with and tested on given_set = [1, 2]: def all_subsets_iter(given_set): subset = [None for n in range(len(given_set))] for i in range(len(given_set)): for j in range(len(subset)): if j == i: subset[i] = None print(subset) else: subset[j] = given_set[j] print(subset)
It's much easier when you realize that all the subsets for a given set can be represented by bits when you count in binary up to 2^n. For example: 000, 001, 010, 011... can represent the subsets for a list of length 3. You can code this in 5 lines in python with no recursion and O(1) memory like so: for i in range(2 ** len(set)): for j in range(len(set)): if i & (1
here's my version in python. I think there is still huge space for improvement... def getsubsets(inputset, n): temparr = [] for i in range(len(inputset)): if i == 0: temparr.append([]) temparr.append([inputset[0]]) else: copy = temparr[:] for x in copy: temparr.append(x+[inputset[i]]) return(temparr) myset = [1,5,15,29] subsets = getsubsets(myset,len(myset)-1) print(subsets)
My method is to first make a int variable say ctr = 0 then create a loop for 2^(number of items) Inside loop - If 1st char in string( ctr) is 1 print first item.also catch string out of index error. Increment ctr by 1. ----_-_-_---_-_-_-_-_-_-_-_-_-_-_-_-_--_ Done, ez
What would sound like nice as a supplementary question is "how to check that the output is correct?". I feel like this is slightly harder but still in reach of many people (even under stress). Does 1h for solving the problem and (programatically) proving the correctness of your function seems reasonable to you guys? In python you could use this function: def subset_generator(E): for i in range(2**len(E)): yield [ E[j] for j in range(len(E)) if (i & 2**j) ] Which you can then call like this to print the subsets: for subset in subset_generator([1,2,3]): print(subset)
def print_all_selections(given_list): /* a selection can be encoded as a bool, a series of selections can be encoded as a vector of bools, a vector of bools can be read as an int by iterating over all ints, we iterate over all possible selections */ n = length( given_list ) boolF = '{0:0' + str(n) + 'b}' def select( idx ): return boolF.format( idx ) | x => zip( list(x), given_list ) .filter( x => x[0] == '1' ) .map( x => x[1] ) for idx in range( 0, 2^n ): select( idx ) | ', '.join | print
I used the following approach: given the set S with n elements...find S^n. aka SXSXS...n times..for every set element in that set, sort it and remove the repeating elements, and remove equivalent set elements after that
Your video is extremely well done, educative and your explanation of the problem and of the algorithm is very effective. In my opinion you achieve even more, actually setting a solid base for understanding the backtracking strategy. Thank you very much
It's a combination problem and one can use itertools in python. But this approach may not be acceptable for SWE interviews. import itertools a = [1,2] ctr = 1 for i in range(0, len(a) + 1): for j in itertools.combinations(a, i): print ctr, len(j), ":", j ctr += 1
Thanks for making a really cool video. This is a great video for showing how to begin to attack a problem and showing the development of a strategy and implementing that strategy. It is great. By the way. In reading the comments... people please remember that this is not intended for master coders that have know every amazing trick. This is how to create a clear solution that fits the requirements. The next thing the interviewer will likely say is "Great solution. So how does this perform? Are there ways that we can optimize this? How would you begin optimization?". To the people saying... "ooo bad... you are fired!". You are why software interviews can be torturous. Programmers with great code skills but with no people skills and the nurturing instincts of a hungry shark are one of the real problem with the industry. Thanks both for the video and trying to nurture other coders!
I am trying to solve a problem for the past one week and being new to competitive programming, it is a tough one for me. The problem states:- Given two binary cyclic sequences(A and B) of equal length 'n'. Our target is to make sequence A to be equal to sequence B. The only implementation that we can do to sequence A is if A(i) is the element at the ith index of sequence A, if we want to flip A(i), then we will also have to flip A(i+1) and A(i+2). So basically at a time we can flip any three consecutive elements of sequence A. Let's call flipping the three elements as a 'move'. Now our target is to make sequence A to be equal to sequence B in the least moves possible. And our output should print out the min. number of moves needed for the same. Please comment below if you'd need more detailing on the problem statement. Any help or hint would be appreciated!
In your pseudo code you can remove one assignment to subset[i] (the first one) if you just call first the recursive call with the current elements and then assign the null value to the current "i" position. Maybe you did it that way to reflect the graph that you are using to explain the solution.
Why not assign a bit to each element and count up in binary until (2^n) -1, creating a new sub array for each iteration. For example, lets say you're given [1, 2] Assign bit_1 to 1 and bit_2 to 2. Then go 00, 01, 10, 11 (bit1bit2). So an array of with no elements is created {} (00), then an array with {2} (01). then one with {1} (10) then one with both{1.2} (11). Not sure how you would code that but if all elements are unique you're essentially looking for all possible combinations of elements.
imho I would prefer to pass set objects to the helper function here since state is not actually important for this particular problem and you can print the sets as-is rather than iterating over the lists to remove the null elements (better runtime efficiency).
Hmmm - are we sure recursion is a good solution here? If we just for loop from 0 to 2^N then we can use the loop counter as a bit-mask to determine whether an element is in the next subset (and print).
my solution on python: def subsets(array): import itertools n=len(array) for i in list(itertools.product("10", repeat=n)): output = "" for j in range(len(i)): if int(i[j]) == 1: output += str(array[j])+"," print(output)
It works, Master... Thx a lot... My case in C language : int main() { int given_array[] = {5, 10, 15, 20}; all_subsets(given_array, 4); //The number '4' is the size of 'give_array' return 0; } void print_set(int subset[], int size) { for (int i = 0; i < size; i++) { printf("%d, ", subset[i]); } printf(" "); } void helper(int given_array[], int size, int subset[], int i) { if (i == size) { print_set(subset, size); } else { subset[i] = 0; helper(given_array, size, subset, i + 1); subset[i] = given_array[i]; helper(given_array, size, subset, i + 1); } } void all_subsets(int given_array[], int size) { int subset[size]; helper(given_array, size, subset, 0); }
I think below iterative solution (in python) might work: def compute_all_subset(arr): allSubset = [] allSubset.append([]) for item in arr: allSubsetLength = len(allSubset) for i in range(0,allSubsetLength): temp = allSubset[i].copy() temp.append(item) allSubset.append(temp) return allSubset
I made a java iterative solution using Boolean bit strings although java is definitely not the best language for this kind of problem. public static void main(String[] args) { int[] values = {1,2,3,4}; subSets(values); } public static void subSets(int[] given_array) { String bString; int length = given_array.length; String formater = "%"+String.valueOf(length)+"s"; for(int i = 0; i < Math.pow(2, length);i++) { bString = String.format(formater, Integer.toBinaryString(i)).replace(" ", "0"); System.out.print("{ "); for(int j = 0; j < length; j++) { if(bString.charAt(j)=='1') { System.out.print(String.valueOf(given_array[j])+" "); } } System.out.print("} "); } }
simple one in python: def genSubsets(L): if len(L)==0: return [[]] #list of empty list smaller=genSubsets(L[:-1]) extra=L[-1:] new=[] for small in smaller: new.append(small+extra) return smaller+new
Thought I would explain the logic... If the example is [1,2] for the given_array then we can assume that subset is [2] because the length is 2. Meaning this array can have 2 elements. So when we call helper for the first time the values are as follows helper ( [1,2] , [_ , _] , 0 ) notice the second variable is the subset, I have defined it as _ which are blanks, because we have not set the values to these elements as of yet. we first check if i(currently 0) is 2 (the length). this is not true so we go to the else subset [0] = null we call helper for the second time and these are the values: helper ( [1,2] , [null, _] , 1 ) i was increased we check if i(currently 1) is 2 this is not true so we go to the else subset [1] = null we call helper a third time and these are the values: helper ( [1,2] , [null, null] , 2 ) i was increased we check if i(currently 2) is 2 this is true! We print the subset - [null, null] we return we go back to when we called helper for the second time, remember these are the current values: helper ( [1,2] , [null, null] , 1 ) i is back to 1 but this time we are setting subset [1] = given_array[1] remeber the else calls helper twice! once when it sets subset to null and second when it sets subset to given_array we call helper a fourth time and these are the values: helper ( [1,2] , [null, 2] , 2 ) i was increased we check if i(currently 2) is 2 this is true! We print the subset - [null, 2] we return we go back to the first time we called helper, remember these are the current values: helper ( [1,2] , [null , 2] , 0 ) i is back to 0 but this time we are setting subset [0] = given_array[0] we call helper a fifth time and these are the values: helper ( [1,2] , [1, 2] , 1 ) i was increased we check if i(currently 1) is 2 this is not true so we go to the else subset [1] = null we call helper a sixth time and these are the values: helper ( [1,2] , [1, null] , 2 ) i was increased we check if i(currently 2) is 2 this is true! We print the subset - [1, null] we return we go back to the fifth time we called helper, remember these are the current values: helper ( [1,2] , [1 , null] , 1 ) i is back to 1 but this time we are setting subset [1] = given_array[1] we call helper a seventh (and last) time and these are the values: helper ( [1,2] , [1, 2] , 2 ) i was increased we check if i(currently 1) is 2 this is true! We print the subset - [1, 2] We are done!! Hope it helped other people viewing this as this question and solution also puzzled me. I am not certain if subset keeps its current values, when returning though. if I had anything wrong in my logic please correct me. Thanks!
Iterative solution. Given a set and a subset of this set, you can interpret this subset as a binary number, for each element in the set: if it's a member of the subset, the value will be 1 and otherwise 0, this is how you build the binary number for a given subset. Which means that you can interpret back the binary number to the subset. The amount of subsets is 2^the length of the big set Let's define: n = length of a given set. There are 2^n binary numbers that can be interpreted to subsets of the set by the method I showed. From the number 0 to the number 2^(n-1). Algorithm. Define n = length of the given set. Define s = an empty set. Loop i from 0 to 2^(n-1): Define b = i in binary. Define sub = interpret i to subset. Add sub to s. End loop. Return s.
Here's a Java iterative version that supports sets of any size (even larger than 64): void printSubsets(int set[]) { final int n = set.length; final BigInteger limit = BigInteger.ONE.shiftLeft(n); System.out.println("-"); for (BigInteger i = BigInteger.ONE; i.compareTo(limit) < 0; i = i.add(BigInteger.ONE)) { for (int j = 0; j < n; j++) { if (i.testBit(j)) { System.out.print("" + set[j] + ","); } } System.out.println(""); } } I don't suggest creating a set of 64 numbers because it'll be printing forever. Well, not forever, but years perhaps?
Let's take a real life example for when finding subsets can be useful. Imagine, you are creating an online restaurant where people can order food and have it delivered. We have a smoothie section in our menu and we want to give the options to customers to pick from available fruits. They have a set of fruits to pick from. Based on the choice of the customer, the app should be able to display the calorie information and display the preset price. For example, Smoothie fruits = {apple, banana, kiwi} In this context, we have to derive the possible combinations that the customer will choose and decide on the price and calories for that mix. • The customer can choose to not have any smoothie. That is encapsulated with an empty subset {} • The following are the possible other combinations ○ {apple} ○ {banana} ○ {kiwi} ○ {apple, banana} ○ {apple, kiwi} ○ {banana, kiwi} ○ {apple, banana, kiwi} Now that we have all available subsets, we can preset the information for the combination(price, name, calorific info) and greatly improve the customer experience!
How about recursively taking members out of the set printSet(list array) { if(array.count == 0) return; foreach(var item in array) { console.write(item.tostring()); console.write(" " ); console.writeline(""); } for(int i = 0; i < array.count; i++) { var tempArray = array; printSet(tempArray.removeAt(i)); } }
For the decision, do you mean the current value is included or not? Or you mean we can chose from 1 or 2, and the number of decisions are 2. If in this case, what about Time complexity of [1,2,3], will that be 3^n?
Excellent video! Please make more videos like this one about coding interview questions. Can you please make one explaining the recursion tree and code for all permutations/combinations of a list (or string)?
Here is a simpler solution: S = [1,2, 3, 4] def update(subsets, e): new_elements = [] for s in subsets: new_elements.append(s+[e]) subsets.extend(new_elements) def subsets(S): subsets = [] #base case subsets.append([]) for e in S: update(subsets, e) return subsets print(subsets(S))
Thx for this! Please show the full working solution written in PY in some editor as that would be extremely beneficial to see that from the beginning till the end.
What if given_array is null? To cover that edge case you need to add the following as the first line in all_subsets function: if (given_array == null) return;
How about using numbers binary representation as an encoding. 00 would mean none of the elements included, 01 would mean only second element included, etc. Then only enumerating the numbers from 0 to 2^n with the right encoding and printing the elements only corresponding to 1s in binary representation of the subset.
from collections import defaultdict def powerset(arr): n = len(arr) s = defaultdict(list) s[0].append([]) for i in xrange(n): for subset in s[i]: s[i + 1].append(subset) s[i + 1].append(subset + [arr[i]]) print s[n]
2^n is the number of combinations possible. So, it is not a matter of work efficiency. At the end, you'll end up doing the same amount of work. However, converting this problem into a iterative solution should be a bit more messy code.
I used this method when coding this, and the only drawback is that you need to construct each subset from the binary number, which means that the time taken is actually, for an array length of n, O(n * 2^n)
It is not a drawback... the number of characters of the output if O(n*2^n). You can not possibly go faster. You have to be careful though : 2^n shouldn't be greater than the greatest integer. To avoid any possible failure, you better use a class that handles integer as large as you want. Another option would be to represent your subset as an array of booleans. Usually, using a recursive function is a bad idea (so I would favor the solution proposed by MarekO). Anyway, this problem is stupid : n*2^n is HUGE and you do not want to do this. So the correct answer to this FaceBook interview should be : "We can do this, but it is a very stupid idea and if implemented it will probably not fit your needs. Rethink your problem."
def allSets(myList): for i in range(1,2**len(myList)): binaryRep = bin(i)[2:] while not len(binaryRep) == len(myList): binaryRep = '0' + binaryRep #print(binaryRep) mySet = list() for j in range(len(binaryRep)): if binaryRep[j] == '1': mySet.append(myList[j]) print(mySet[:]) This is a code I came up with using other people's ideas of binary representation
Here is my python solution def genSubset(L): """ Generates the subsets of a set given in an array form. It starts with the empty set and adds a new element of the set to the previous subsets iteratively to create new subsets, and then combines the new and previous subsets... """ subsets=[[]] newsubsets=[] for i in L: for s in subsets: newsubsets+=[s+[i]] subsets=subsets+newsubsets newsubsets=[] return subsets
A much more understandable approach (IMO) would be: ``` arr = [1,2,3] subsets = [[]] for a in arr: subsets = subsets + [b + [a] for b in subsets] print(subsets) ``` At each step, you take the entire subsets list from one index below *unchanged*, then *another copy* of it with ith element added to each subset. OR if we want recursive solution, ``` def foo(arr): if len(arr) == 0: return [[]] else: prev_subsets = foo(arr[:-1]) return prev_subsets + [a + [arr[-1]] for a in prev_subsets] print(foo([1,2,3])) ```
honestly, it is not that the problem cannot be solved. If I am faced with this problem in real life like as a homework problem, I might get stuck for the first 10 minutes, and then I might put it down, do something else, maybe have lunch, and then I think of something, and then I try it, and yes, I was able to solve it the second time I thought about it, using the binary representation... so I can solve it... it is just that within that 20 minutes per interview question time frame, you might not show a solution like a straight line from point A to point B. So does that mean you are not good? I am sure many programmers, they might do something in the morning, and in the afternoon or the next day, they thought, hold on a second, there is a much better way! Does that mean they are not good, because they don't give the perfect solution in a 20 minute time frame?
my first thought is using dynamic programming, dp[n][ ]=dp[ n-1][ ]+(dp[ n-1][ ]+given_array[n])//plus in here means print it's more straightforward for me.
I was struggling it using a BTS, at the end I came up with a mix (but basically, the magic in here is iterate the array recursively instead of using a loop function. This is my solution class SubSet{ constructor(content = []) { this.content = content; this.left = null; this.right = null; } } function helper(array, set, i) { if (array.length === i) { console.log(set.content); } else{ set.left = new SubSet(set.content.concat(array[i])); helper(array, set.left, i + 1); set.right = new SubSet(set.content); helper(array, set.right, i + 1); } } helper([1,2,3,4,5,6], new SubSet, 0);
![SAFEPLANET - ดาวเคราะห์ [ THE PLANET ]](http://i.ytimg.com/vi/4X1XL3I_k3c/mqdefault.jpg)
Thanks as always for watching this video guys!
If there is any other interview question you'd like me to cover in the future, you can (anonymously) let me know at this link here :) -> www.csdojo.io/contribute
CS Dojo hey man which programming languages don't have maths
Parikshit Patil lol
I am very weak at maths that's why ?
well in every language there is a maths so 🙄 .just try to stick with the problem. 😁✌
You are great Sir, heads off to you
If it's an interview for Facebook, make sure to print an ad between each set for bonus points.
this ^^ 😂
Alien OrSutin haha
good point
You are hired
now ur know how to crack facebook interview😂
I have a message for anyone who sees this examples as difficult:
Don't let your brain fool you. When encountering something we don't know, our brain is extremely, EXTREMELY good at convincing us that given task is either: too complicated for us, too boring for us or both. See through it. Look at the whole picture. For example. You have some skills that are easy for you now. Let's say typing on keyboard. Do you remember how hard it was in the beginning of developing that skill? And how your brain made same assumptions about what you are doing, that this is maybe stupid, or boring, and who the fuck placed those stupid keys in this non alphabetical order?. Try to remember exactly that feeling, then how you overcome it, and how it is easy for you now. Same shit here. Your brain is tricking you. It's not subject, it's just automatic reaction of our brain. See through it, persevere. It'll be hard, starting learning programming is hard, but in the end, you'll do it with fucking excitement and pleasure, I'm telling you. I was absolutely dumb at school, i didn't know what PI is in mathematics, fucking multiplying two digit numbers was my peak achievement. But. I always believed that if I'll decide firmly enough, I can learn anything, because anything can be interesting, extremely interesting, if you put enough focus and effort in it. Five years later, I'm middle Java developer of web applications. I did it, so can you.
inspiring!
thank u sir
Well said Bravo ...👏
Hi Kolos,
I came in comment section to see comments where people say it helped alot, they got the concept very clearly and then hate myself that why I am not getting it, this is not my cup of tea.I was almost about to leave it... but I found your comment, now I'll again go through the video and finish it when I'll get it in my mind :)
Noopur dubey keep it up :)
There's a way elegant way to solve it with a binary representation of the input array.
Since the elements in the array are unique they can be represented as 0 or 1 (present or NOT present).
Lets say we have an array [1, 3, 5, 7].
array[0] = 1;
array[1] = 3;
array[2] = 5;
array[3] = 7;
All we need to to is to define a printing method that prints all entries where 1 is on in the binary representation of our iteration.
In our example, the subsets can be represented by all the binary options from 0 to 4 (decimal, the array size) are:
0000 = {}
0001 = {1}
0010 = {3}
0011 = {1, 3}
0100 = {5}
0101 = {1, 5}
0110 = {3, 5}
0111 = {1, 3, 5}
and so on, till we get to 2^n options, in our case - 2^4 = 16 permutations.
1111= {1, 3, 5 ,7}
#python solution for this approach
def subsets_binary_way(array):
for i in range( pow(2,len(array))):
binary_array = [int(j) for j in bin(i)[2:]]
zero_array = [0]*(len(array) - len(binary_array))
binary_array_full = zero_array + binary_array
sub_array = [array[k]*binary_array_full[k] for k in range(len(binary_array_full))]
print([i for i in sub_array if i !=0])
how de we make that printing method to print all entries where 1 is on in the binary representation of our iteration?
The solution is brilliant, but it may not be optimised in time complexity.
@@AkshayKumar-pf1qf nice one! you inspired me. here is my implementation.
```
def subsets_binary_way(array):
for i in range(2 ** len(array)):
bs = bin(i)[2:].zfill(len(array))
print([array[k] for k in range(len(bs)) if bs[k] == '1'])
```
@@promamukherjee5874 aren't both solution O(n**2)? What optimization can you do to lower this?
I wanted to share an iterative approach that I thought about while watching this video. Consider an example where you have eight elements. The total number of possible combinations is 2^8 (256). If we were going to use a for loop in C++, your loop might look like this: for(int i = 0; i < 256; i++). If you covert the index of 'i' into binary, you can visualize this as switches that tell you which elements to print out. For example, the last combination you print out will be where 'i' is equal to 255. That can be represented in binary as 1111 1111. Each index of this binary number represents an index in your initial array and as you look through this binary number from left to right, if the index is 1 then you print out the associated value from the array.
Thats Clever Thanks
Dear Matthew, Yes, your method is way clearer than CJ DoJo's method. But still, both CJ DoJo's and your method are inefficient.
For example, CJ DoJo's method is those method circulating on the internet. But it has a few serious flaws;
1. In real applications, we do not need to construct all subjects. For example, if we are given a set of 4 elements S = { a, b, c, d}, and we usually want to construct subsets with a specific number of elements, such as two or three, but not all subjects.
2. If we are to use either your method or CJ DoJo's method, we have to iterate 2^(number of elements, in this case 4) times only to construct subsets with a specific number of elements. It's a huge waste of computing resource.
3. CJ DoJo's method is not PARALLELIZABLE.
4. CJ DoJo's method is a recursive method, which is awfully slow and inefficient.
Whereas, I implemented subset constructions using nCr = n-1Cr-1 + n-1Cr equality, both using recursion and loop. Of course, the loop method is much faster. th-cam.com/video/9rZMqwW52D0/w-d-xo.html
My method is parallelizeable and base on Loop. The biggest advantage of this method is that instead of enumerating all subjects with a specific number of elements, we can construct the k-th subset with r elements, where 0
any sample Matthew
Good job
@@HomoSiliconiens Good
This Worked for me in Python:
a = int(input("Enter Range:"))
ss=[]
b1=[]
lst=[]
ss1=[]
ss2=[]
for t in range(a):
b = int(input())
b1.append(b)
b1_len = len(b1)
for i in range(0,b1_len):
for j in range(i+1,b1_len):
lst = [b1[i],b1[j]]
ss.append(lst)
for t in range(0,a):
ss.append(b1[t])
ss.append(ss1)
print(ss)
Since we're printing out the power set of the original set, this is the shortest solution you can find
for i = 0 to 2^n:
print binary_representation_of(i) * original_set;
great solution! :)
This blew my mind. I need to step up my bit manipulation game.
how does this multiplication works?
@@yanbala30 for each set xth bit print xth element
that's a good solution for n < 32 or 64, if the n is too big, say the length of the set is 128 or more, this solution might be tough to be implemented
here's my solution
it uses the fact that the subsets of, for eg. [3,5,7], will always be (subsets of [5,7] + [append 3 in every subset of [5,7])
(p.s. this is also a way to understand why the power set of n+1 elements is always 2 times the size of power set of n elements)
The code(Python3):
def get_all_subsets(s):
subsets = []
if len(s) == 0:
subsets.append([])
else:
s_copy = s.copy()
first_element = s_copy.pop(0)
subsets += [x for x in get_all_subsets(s_copy)]
subsets += [[first_element, *x] for x in get_all_subsets(s_copy)]
return subsets
print(get_all_subsets([5, 7, 8]))
I have implemented this using java. It is a wonderful approach. Thanks dude. Below is the implementation:
public class FindAllSubsets {
public static void printAllSubsets(int[] array) {
int[] subset = new int[array.length];
helper(array,subset,0);
}
private static void helper(int[] array,int[] subset,int i) {
if(i==array.length)
print(subset);
else {
subset[i]=0;
helper(array, subset, i+1);
subset[i]=array[i];
helper(array,subset,i+1);
}
}
private static void print(int[] subset) {
boolean flag=false;
for(int i:subset) {
if(i!=0) {
flag=true;
System.out.print(i+",");
}
}
if(!flag)
System.out.print("-");
System.out.println();
}
public static void main(String[] args) {
int[] arr = {1,2};
printAllSubsets(arr);
}
}
subset must not include {1,3} as its not contiguous
i think im gonna work at mcdonalds
Don't let your brain fool you. When encountering something we don't know, our brain is extremely, EXTREMELY good at convincing us that given task is either: too complicated for us, too boring for us or both. See through it. Look at the whole picture. For example. You have some skills that are easy for you now. Let's say typing on keyboard. Do you remember how hard it was in the beginning of developing that skill? And how your brain made same assumptions about what you are doing, that this is maybe stupid, or boring, and who the fuck placed those stupid keys in this non alphabetical order?. Try to remember exactly that feeling, then how you overcome it, and how it is easy for you now. Same shit here. Your brain is tricking you. It's not subject, it's just automatic reaction of our brain. See through it, persevere. It'll be hard, starting learning programming is hard, but in the end, you'll do it with fucking excitement and pleasure, I'm telling you. I was absolutely dumb at school, i didn't know what PI is in mathematics, fucking multiplying two digit numbers was my peak achievement. But. I always believed that if I'll decide firmly enough, I can learn anything, because anything can be interesting, extremely interesting, if you put enough focus and effort in it. Five years later, I'm middle Java developer of web applications. I did it, so can you.
A lot better decision would be to program those robots that will serve food in McDonalds in five years ;)
Kolos great reply and very insightful!
you are so nice
problems solved, repeat, repeat and repeat
I rarely give compliments bc I always have something that bothers me about the video (i don't compliment tech videos) but WOW!!!! you're exceptional. your videos are AMAZING!!!! I have a physics degree went into DS/ML like most of us do and now I'm switching to CS. Your videos are so clear cut your speech is impeccable, perfect pace, sound and visual, and a nice flow. I can tell you did multiple takes or practice (if not that's REALLY impressive). combined with all you have a great knowledge base and present it *flawlessly*. Most of my interviews were things you covered and your videos are also the right amount of time. It's short enough to maintain interest and long enough to give you thoroughly. It's kind of a shame that people will only really tune in during interviews or when they are learning CS/DS. You structured it well with depth and breadth. You go into a great overview and then have videos that go into more specific which is WAY better than having one long video. I wish I saw these videos before just doing a bunch of leetcode problems. It's a great clean organized way of explaining the tools. I didn't know how many leetcode problems were enough but this is great! I used your info so much on interviews. It's so memorable and keeps my attention (I have ADHD so I'm really picky with videos). I'll definitely share your channel with people interviewing or anyone new to coding. If you decide to leave TH-cam please keep these videos up. Also, you don't have that annoying "Aren't you amazed how smart I am?" arrogant vibe. You have a very humble, enthusiastic energy. Okay, this comment is way too long it's kind of creepy, but I'm a girl so how dangerous can I be? I just really wanted to let you know your videos are powerful and I really appreciate the time you take to edit them, it makes watching/learning so much easier. I know it's a lot of effort and it might not be obvious to people watching bc we're so focused on learning but I thought you should know it sets you apart.
Also, I actually was mainly referring to the videos about databases and algorithms. But I was on this video so iI commented here. I can copy and paste it there thought. I realized what I said might not seem as relevant as it does for the other ones I watched multiple times. (that sounds creepy but it's to really solidify the information and go back to see your code or your examples etc. it's not the whole thing.
How about this solution ?
Since we know the number of subsets
Represent that number in its binary form and essentially go from 0 till that number - 1.
For the above example
Now we start with 00 and go all the way till 11 where each position denotes the element and 1 denotes it’s included
So for e.g. : [1,2]
00 : []
01 : [2]
10 : [1]
11 : [1,2]
You got the values of 1, and 2 (namely 01, and 10, respectively) backwards in your explanation.
@@CharlieZuko he explained everything correct, there is no error. 01 = 2 cause he took 2nd element from array [1,2] which is 2
Great Thinking Bro.
Dang that's some creative stuff!! Much respect
The thing is if you desire to print all subsets, you have to go in the array from start to end in each subset, how would you handle it?, unless a hashmap would be used. xd
Use a Map map to arrive at an iterative solution. The key stores the index for visited elements in array i,e 0,1,2...etc.
The String[] stores different possible string with all previous map values.
Time complexity should be O(n * log(n)).
Print all the values for each key and you should have all the subsets
If you are looking at all previous values in hashtable, wont total operations be 1+2+...+n= O(n^2)
This was awesome!
For an iterative solution, I built out a tree. When the added node had a depth == len(passed_array) I added that node to a list. The data of each node contained the full set up to that point, so at the end, I was able to iterate through each node in the list of final-sets and call print on it.
Simple iterative solution
val set = mutableSetOf(setOf())
listOf(1,2,3).forEach {next ->
set += set.map { it + next }
}
For n=0 to 2^n, convert n to a binary number. Create mapping from each binary value to the set. If 0 don't include in output, if 1 include in output.
If , say you are given an eight element set: make a list of all possible 8-bit binary strings and wherever 1 occurs in the string, that is the index of the element from the set that we should include in our list , the take the union(possible to do in python) and print .
Caution: the subset array must be passed by value, otherwise, when the recursion returns at the second call to helper, the value of subset array will be different as the first call to helper overwrote it
My first thought was masking the elements of the array with a binary number. (I think someone else may have seen this solution too). The solution becomes counting to 2 to the power of elements in the array and at each step, mask the elements of the array with the binary number. 0 means dont print the element, 1 means do print it.
eg for his example we're counting to 4 and masking with {0,0}, {0,1}, {1,0}, {1,1) resulting in the empty array for {0,0), {2} because the "1" element is masked out from {1,2} when you apply {0,1} to it and so on. Minimal memory needed.
You are really good. The complexity is explained in a very simple way. Shout out to you.
from itertools import combinations
x = [1, 2]
y = []
for i in range(len(x)+1):
y.append(list(combinations(x, i)))
print(y)
BOOM! DONE!
There's an iterative approach that's much easier and doesn't require keeping track of any nulls. Here it is coded in python:
def printAllSubsets(givenArray):
subsets = [[]]
print(subsets[0])
for i in givenArray:
for j in range(len(subsets)):
newSubset = subsets[j][:]
newSubset.append(i)
subsets.append(newSubset)
print(newSubset)
printAllSubsets([1,2])
That does'nt work. The # of subsets it should print is 2**n where n is the number of items in the array.
Have a facebook swe interview soon! I know it's not going to be the same questions but this is helping me brush up so thank you!!
Charms So did you make it??
Were the questions to you similar to this?
I guess s/he got rejected and committed suicide
@@farazahmed7 xD
We can also replace 2^n with (1+1+(nc1+-------+nc(n-1)) and create a function which prints null and complete set first. Then iterate the rest of the times to print subset containing (1,2,3 and so on) element in a set. U will exactly have same number of subsets of a particular combination as you want using (nc(r-1)).
It can be solved by binary coding. We use n sized binary code. The permutation of the code is 2^n. We simply iterate from 0 to 2^n-1 and for each number get the bits of the number. The binary form of this each number represents one subset.
The bits of the number represents if any element of data is included in the set or not. Simply put, if i'th bit is 1 then i'th element in the input data is included in this subset and vice versa.
The iterative approach is a beautiful solution. Check out for it to get mesmerised with its beauty.
An iterative can solution can be traversing number from 0 to 2^n. For each number get binary bits (0 or 1). If it's 1 - print a number in the corresponding postion of given_array.
Generate all int between 0 and 2^n-1. The binary representation of the int tells if an element should be included in the subset. If bit X is set, include the number at position X. Otherwise, skip it.
Thanks for visualizing the recursion tree, it gave me an idea how to solve this, but I couldn't put it into words till I finished watching the video.
I've made an iterative solution using Javascript. At each step, it makes a decision whether to add an item to current combination or not. This significantly simplified the code I was trying to write, thanks for all the tips! Code:
function powerSet(inputs) {
const results = [];
const stack = [[[], 0]];
while(stack.length > 0) {
const [combination, index] = stack.pop();
// we have reached the final index of combination, push to results and exit
if (index === inputs.length) {
results.push(combination);
continue;
}
// do not add current element, make a copy of existing combination and push it to stack
stack.push([[...combination], index + 1]);
// add current element to combination and push it to stack
combination.push(inputs[index]);
stack.push([combination, index + 1]);
}
return results;
};
Hello Mr. Dojo, I like the way you explain the algorithm. Here is my solution in java:
public void printSubSet(String[] numArray) {
String[] oldList = {""};
for (int i = 0; i < numArray.length; i++) {
String[] ar = new String[oldList.length * 2];
for (int j = 0; j < ar.length; j++) {
if (j < oldList.length) {
ar[j] = oldList[j];
} else {
ar[j] = oldList[j - oldList.length] + numArray[i];
}
}
oldList = ar;
}
System.out.println("Printing subset : " + Arrays.toString(oldList));
System.out.println("Number of subset : " + oldList.length);
}
from functools import reduce
def power_set(array):
return reduce(lambda subsets, i: subsets + list(map(lambda x: x + [array[i]], subsets)), range(len(array)), [[]])
# One way to utilize recursion for this task in Python:
def get_all_sets(elts):
if elts:
if len(elts) > 1:
remaining = get_all_sets(elts[1:])
return [*remaining, *[[elts[0]]+r for r in remaining]]
else:
return [[], elts]
return [[]]
# Test
print(get_all_sets([]))
print(get_all_sets([1]))
print(get_all_sets([1, 2]))
print(get_all_sets([1, 2, 3]))
print(get_all_sets([1, 2, 3, 4]))
# I used lists as arguments for simplicity and ease of algorithm understanding.
Recursion is the key. Recursion uses the memory stack. So if we could somehow make use of the stack data structure, the problem can be solved in iterations.
Yes, I don't think there can be any other way, as there is only top-down approach available for this problem but not the bottom-up. So it should be done using a stack. Did you try it out?
I believe a queue can also be used depending on how you want to traverse the tree.
for the iterative solution, use a stack to do the pre-order tree traversal
I simple iterative approach would be to iterate from 0 to 2^n and for each num check if any bit is set among ciel(log(x)) bits , for each set bit print the element . This way you will get a subset for each x.
Iterative solution I came up with and tested on given_set = [1, 2]:
def all_subsets_iter(given_set):
subset = [None for n in range(len(given_set))]
for i in range(len(given_set)):
for j in range(len(subset)):
if j == i:
subset[i] = None
print(subset)
else:
subset[j] = given_set[j]
print(subset)
3rd times the charm! That 3rd bracket is one of the most beautiful brackets I've seen haha
Iterative approach is very simple, just use binary numbers of 2^(len(arr)) bits
It's much easier when you realize that all the subsets for a given set can be represented by bits when you count in binary up to 2^n. For example: 000, 001, 010, 011... can represent the subsets for a list of length 3. You can code this in 5 lines in python with no recursion and O(1) memory like so:
for i in range(2 ** len(set)):
for j in range(len(set)):
if i & (1
But this wont print the subsets in lexicographic order
here's my version in python. I think there is still huge space for improvement...
def getsubsets(inputset, n):
temparr = []
for i in range(len(inputset)):
if i == 0:
temparr.append([])
temparr.append([inputset[0]])
else:
copy = temparr[:]
for x in copy:
temparr.append(x+[inputset[i]])
return(temparr)
myset = [1,5,15,29]
subsets = getsubsets(myset,len(myset)-1)
print(subsets)
My method is to first make a int variable say ctr = 0
then create a loop for 2^(number of items)
Inside loop - If 1st char in string( ctr) is 1 print first item.also catch string out of index error.
Increment ctr by 1.
----_-_-_---_-_-_-_-_-_-_-_-_-_-_-_-_--_
Done, ez
What would sound like nice as a supplementary question is "how to check that the output is correct?". I feel like this is slightly harder but still in reach of many people (even under stress). Does 1h for solving the problem and (programatically) proving the correctness of your function seems reasonable to you guys?
In python you could use this function:
def subset_generator(E):
for i in range(2**len(E)):
yield [ E[j] for j in range(len(E)) if (i & 2**j) ]
Which you can then call like this to print the subsets:
for subset in subset_generator([1,2,3]):
print(subset)
How are you suppose to come up with this solution during an interview?
def print_all_selections(given_list):
/* a selection can be encoded as a bool,
a series of selections can be encoded as a vector of bools,
a vector of bools can be read as an int
by iterating over all ints, we iterate over all possible selections */
n = length( given_list )
boolF = '{0:0' + str(n) + 'b}'
def select( idx ):
return boolF.format( idx )
| x => zip( list(x), given_list )
.filter( x => x[0] == '1' )
.map( x => x[1] )
for idx in range( 0, 2^n ):
select( idx ) | ', '.join | print
I used the following approach:
given the set S with n elements...find S^n. aka SXSXS...n times..for every set element in that set, sort it and remove the repeating elements, and remove equivalent set elements after that
Your video is extremely well done, educative and your explanation of the problem and of the algorithm is very effective. In my opinion you achieve even more, actually setting a solid base for understanding the backtracking strategy. Thank you very much
recursion...is beautiful.
iterative approach:
public void PowerSet(int[] array)
{
int length = array.Length;
int totalSubSet = Math.Power(2, length) - 1;
for(int i = 0; i < totalSubSet; I++)
{
List powerSet = new List();
for(int k = 0; k< length; k++)
{
bool isExists = (i >> ((length - 1) - k)) && 1;
if(isExists)
{
powerSet.Add(array[k]);
}
}
Console.WriteLine(powerSet);
}
}
It's a combination problem and one can use itertools in python. But this approach may not be acceptable for SWE interviews.
import itertools
a = [1,2]
ctr = 1
for i in range(0, len(a) + 1):
for j in itertools.combinations(a, i):
print ctr, len(j), ":", j
ctr += 1
Your teaching style is owesome
Please complete video series on dynamic programming and so on....
Yes atleast a couple of more coding questions on dynamic programming
Thanks for making a really cool video. This is a great video for showing how to begin to attack a problem and showing the development of a strategy and implementing that strategy. It is great. By the way. In reading the comments... people please remember that this is not intended for master coders that have know every amazing trick. This is how to create a clear solution that fits the requirements. The next thing the interviewer will likely say is "Great solution. So how does this perform? Are there ways that we can optimize this? How would you begin optimization?". To the people saying... "ooo bad... you are fired!". You are why software interviews can be torturous. Programmers with great code skills but with no people skills and the nurturing instincts of a hungry shark are one of the real problem with the industry.
Thanks both for the video and trying to nurture other coders!
crystal clear explanation, well done....
I am trying to solve a problem for the past one week and being new to competitive programming, it is a tough one for me. The problem states:-
Given two binary cyclic sequences(A and B) of equal length 'n'. Our target is to make sequence A to be equal to sequence B. The only implementation that we can do to sequence A is if A(i) is the element at the ith index of sequence A, if we want to flip A(i), then we will also have to flip A(i+1) and A(i+2). So basically at a time we can flip any three consecutive elements of sequence A. Let's call flipping the three elements as a 'move'. Now our target is to make sequence A to be equal to sequence B in the least moves possible. And our output should print out the min. number of moves needed for the same.
Please comment below if you'd need more detailing on the problem statement. Any help or hint would be appreciated!
In your pseudo code you can remove one assignment to subset[i] (the first one) if you just call first the recursive call with the current elements and then assign the null value to the current "i" position. Maybe you did it that way to reflect the graph that you are using to explain the solution.
I really like this kinda of coding interview videos, can you do more of these please?
Why not assign a bit to each element and count up in binary until (2^n) -1, creating a new sub array for each iteration. For example, lets say you're given [1, 2] Assign bit_1 to 1 and bit_2 to 2. Then go 00, 01, 10, 11 (bit1bit2). So an array of with no elements is created {} (00), then an array with {2} (01). then one with {1} (10) then one with both{1.2} (11). Not sure how you would code that but if all elements are unique you're essentially looking for all possible combinations of elements.
this is a very basic backtracking problem. You should refer to the stanford lecture on backtracking, they have a beautiful formula there.
can u post the link here pls?
Create a binary number the same length as the given array, then increment it, logging the set represented by the bits which are 1.
How do you handle "all combinations of 4 six-sided dice rolls"?
Awsome man..You made it look clear
You gained 4k subs over the night lol
imho I would prefer to pass set objects to the helper function here since state is not actually important for this particular problem and you can print the sets as-is rather than iterating over the lists to remove the null elements (better runtime efficiency).
Hmmm - are we sure recursion is a good solution here? If we just for loop from 0 to 2^N then we can use the loop counter as a bit-mask to determine whether an element is in the next subset (and print).
my solution on python:
def subsets(array):
import itertools
n=len(array)
for i in list(itertools.product("10", repeat=n)):
output = ""
for j in range(len(i)):
if int(i[j]) == 1:
output += str(array[j])+","
print(output)
It works, Master... Thx a lot... My case in C language :
int main() {
int given_array[] = {5, 10, 15, 20};
all_subsets(given_array, 4); //The number '4' is the size of 'give_array'
return 0;
}
void print_set(int subset[], int size) {
for (int i = 0; i < size; i++) {
printf("%d, ", subset[i]);
}
printf("
");
}
void helper(int given_array[], int size, int subset[], int i) {
if (i == size) {
print_set(subset, size);
}
else {
subset[i] = 0;
helper(given_array, size, subset, i + 1);
subset[i] = given_array[i];
helper(given_array, size, subset, i + 1);
}
}
void all_subsets(int given_array[], int size) {
int subset[size];
helper(given_array, size, subset, 0);
}
I think below iterative solution (in python) might work:
def compute_all_subset(arr):
allSubset = []
allSubset.append([])
for item in arr:
allSubsetLength = len(allSubset)
for i in range(0,allSubsetLength):
temp = allSubset[i].copy()
temp.append(item)
allSubset.append(temp)
return allSubset
I made a java iterative solution using Boolean bit strings although java is definitely not the best language for this kind of problem.
public static void main(String[] args)
{
int[] values = {1,2,3,4};
subSets(values);
}
public static void subSets(int[] given_array)
{
String bString;
int length = given_array.length;
String formater = "%"+String.valueOf(length)+"s";
for(int i = 0; i < Math.pow(2, length);i++)
{
bString = String.format(formater, Integer.toBinaryString(i)).replace(" ", "0");
System.out.print("{ ");
for(int j = 0; j < length; j++)
{
if(bString.charAt(j)=='1')
{
System.out.print(String.valueOf(given_array[j])+" ");
}
}
System.out.print("}
");
}
}
simple one in python:
def genSubsets(L):
if len(L)==0:
return [[]] #list of empty list
smaller=genSubsets(L[:-1])
extra=L[-1:]
new=[]
for small in smaller:
new.append(small+extra)
return smaller+new
super smart. thank you!
Thought I would explain the logic...
If the example is [1,2] for the given_array
then we can assume that subset is [2] because the length is 2. Meaning
this array can have 2 elements.
So when we call helper for the first time the values are as follows
helper ( [1,2] , [_ , _] , 0 ) notice the second variable is the subset,
I have defined it as _ which are blanks, because we have not set the
values to these elements as of yet.
we first check if i(currently 0) is 2 (the length).
this is not true so we go to the else
subset [0] = null
we call helper for the second time and these are the values:
helper ( [1,2] , [null, _] , 1 ) i was increased
we check if i(currently 1) is 2
this is not true so we go to the else
subset [1] = null
we call helper a third time and these are the values:
helper ( [1,2] , [null, null] , 2 ) i was increased
we check if i(currently 2) is 2
this is true! We print the subset - [null, null]
we return
we go back to when we called helper for the second time, remember these
are the current values:
helper ( [1,2] , [null, null] , 1 ) i is back to 1
but this time
we are setting subset [1] = given_array[1]
remeber the else calls helper twice! once when it sets subset to null
and second when it sets subset to given_array
we call helper a fourth time and these are the values:
helper ( [1,2] , [null, 2] , 2 ) i was increased
we check if i(currently 2) is 2
this is true! We print the subset - [null, 2]
we return
we go back to the first time we called helper, remember these are the
current values:
helper ( [1,2] , [null , 2] , 0 ) i is back to 0
but this time
we are setting subset [0] = given_array[0]
we call helper a fifth time and these are the values:
helper ( [1,2] , [1, 2] , 1 ) i was increased
we check if i(currently 1) is 2
this is not true so we go to the else
subset [1] = null
we call helper a sixth time and these are the values:
helper ( [1,2] , [1, null] , 2 ) i was increased
we check if i(currently 2) is 2
this is true! We print the subset - [1, null]
we return
we go back to the fifth time we called helper, remember these are the
current values:
helper ( [1,2] , [1 , null] , 1 ) i is back to 1
but this time
we are setting subset [1] = given_array[1]
we call helper a seventh (and last) time and these are the values:
helper ( [1,2] , [1, 2] , 2 ) i was increased
we check if i(currently 1) is 2
this is true! We print the subset - [1, 2]
We are done!! Hope it helped other people viewing this as this question
and solution also puzzled me. I am not certain if subset keeps its current
values, when returning though. if I had anything wrong in my logic please
correct me. Thanks!
Thanks for the explanation, but i'm still not quite understand why do we return to i = 1 after i = 2 shouldn't the code end after i = 2?
Iterative solution.
Given a set and a subset of this set, you can interpret this subset as a binary number, for each element in the set: if it's a member of the subset, the value will be 1 and otherwise 0, this is how you build the binary number for a given subset.
Which means that you can interpret back the binary number to the subset.
The amount of subsets is 2^the length of the big set
Let's define: n = length of a given set.
There are 2^n binary numbers that can be interpreted to subsets of the set by the method I showed.
From the number 0 to the number 2^(n-1).
Algorithm.
Define n = length of the given set.
Define s = an empty set.
Loop i from 0 to 2^(n-1):
Define b = i in binary.
Define sub = interpret i to subset.
Add sub to s.
End loop.
Return s.
Here's a Java iterative version that supports sets of any size (even larger than 64):
void printSubsets(int set[]) {
final int n = set.length;
final BigInteger limit = BigInteger.ONE.shiftLeft(n);
System.out.println("-");
for (BigInteger i = BigInteger.ONE; i.compareTo(limit) < 0; i = i.add(BigInteger.ONE)) {
for (int j = 0; j < n; j++) {
if (i.testBit(j)) {
System.out.print("" + set[j] + ",");
}
}
System.out.println("");
}
}
I don't suggest creating a set of 64 numbers because it'll be printing forever. Well, not forever, but years perhaps?
Beautifully explained. Though I knew the solution but the idea behind that was not that much clear. Thanks !!
Which language did you get syntax from subset = new int[given_array.length]? python does it like subset = [None]*len(given_array)
Wonderful video. Keep Going Sir... We are always there to support you... Thank you so much for this enlightening video. I am learning a lot from you.
Let's take a real life example for when finding subsets can be useful. Imagine, you are creating an online restaurant where people can order food and have it delivered. We have a smoothie section in our menu and we want to give the options to customers to pick from available fruits. They have a set of fruits to pick from. Based on the choice of the customer, the app should be able to display the calorie information and display the preset price.
For example,
Smoothie fruits = {apple, banana, kiwi}
In this context, we have to derive the possible combinations that the customer will choose and decide on the price and calories for that mix.
• The customer can choose to not have any smoothie. That is encapsulated with an empty subset {}
• The following are the possible other combinations
○ {apple}
○ {banana}
○ {kiwi}
○ {apple, banana}
○ {apple, kiwi}
○ {banana, kiwi}
○ {apple, banana, kiwi}
Now that we have all available subsets, we can preset the information for the combination(price, name, calorific info) and greatly improve the customer experience!
Incredible how easy these are. Thank you for sharing!
so why u here?
thank you this is very helpful
How about recursively taking members out of the set
printSet(list array)
{
if(array.count == 0)
return;
foreach(var item in array)
{
console.write(item.tostring()); console.write(" " ); console.writeline("");
}
for(int i = 0; i < array.count; i++)
{
var tempArray = array;
printSet(tempArray.removeAt(i));
}
}
For the decision, do you mean the current value is included or not? Or you mean we can chose from 1 or 2, and the number of decisions are 2. If in this case, what about Time complexity of [1,2,3], will that be 3^n?
Excellent video! Please make more videos like this one about coding interview questions. Can you please make one explaining the recursion tree and code for all permutations/combinations of a list (or string)?
Here is a simpler solution:
S = [1,2, 3, 4]
def update(subsets, e):
new_elements = []
for s in subsets:
new_elements.append(s+[e])
subsets.extend(new_elements)
def subsets(S):
subsets = []
#base case
subsets.append([])
for e in S:
update(subsets, e)
return subsets
print(subsets(S))
Thank you. You are awesome at programming, sir.
Thx for this! Please show the full working solution written in PY in some editor as that would be extremely beneficial to see that from the beginning till the end.
What if given_array is null?
To cover that edge case you need to add the following as the first line in all_subsets function:
if (given_array == null) return;
How about using numbers binary representation as an encoding. 00 would mean none of the elements included, 01 would mean only second element included, etc. Then only enumerating the numbers from 0 to 2^n with the right encoding and printing the elements only corresponding to 1s in binary representation of the subset.
from collections import defaultdict
def powerset(arr):
n = len(arr)
s = defaultdict(list)
s[0].append([])
for i in xrange(n):
for subset in s[i]:
s[i + 1].append(subset)
s[i + 1].append(subset + [arr[i]])
print s[n]
Just iterate over all binary numbers
2^n is the number of combinations possible. So, it is not a matter of work efficiency. At the end, you'll end up doing the same amount of work. However, converting this problem into a iterative solution should be a bit more messy code.
This is what I thought of first too, can anyone think of any significant drawbacks
I used this method when coding this, and the only drawback is that you need to construct each subset from the binary number, which means that the time taken is actually, for an array length of n, O(n * 2^n)
...edited to delete, as I saw a similar solution that made this idea more clear.....
It is not a drawback... the number of characters of the output if O(n*2^n). You can not possibly go faster.
You have to be careful though : 2^n shouldn't be greater than the greatest integer. To avoid any possible failure, you better use a class that handles integer as large as you want. Another option would be to represent your subset as an array of booleans.
Usually, using a recursive function is a bad idea (so I would favor the solution proposed by MarekO).
Anyway, this problem is stupid : n*2^n is HUGE and you do not want to do this.
So the correct answer to this FaceBook interview should be :
"We can do this, but it is a very stupid idea and if implemented it will probably not fit your needs. Rethink your problem."
def allSets(myList):
for i in range(1,2**len(myList)):
binaryRep = bin(i)[2:]
while not len(binaryRep) == len(myList):
binaryRep = '0' + binaryRep
#print(binaryRep)
mySet = list()
for j in range(len(binaryRep)):
if binaryRep[j] == '1':
mySet.append(myList[j])
print(mySet[:])
This is a code I came up with using other people's ideas of binary representation
Great explanation 👍
Here is my python solution
def genSubset(L):
"""
Generates the subsets of a set given in an array form.
It starts with the empty set and adds a new element of the set
to the previous subsets iteratively to create new subsets, and then combines
the new and previous subsets...
"""
subsets=[[]]
newsubsets=[]
for i in L:
for s in subsets:
newsubsets+=[s+[i]]
subsets=subsets+newsubsets
newsubsets=[]
return subsets
Quite helpful. Many thanks for the lesson.
Great Vid!! Glad I've found your channel :)
That's dope bud!!
A much more understandable approach (IMO) would be:
```
arr = [1,2,3]
subsets = [[]]
for a in arr:
subsets = subsets + [b + [a] for b in subsets]
print(subsets)
```
At each step, you take the entire subsets list from one index below *unchanged*, then *another copy* of it with ith element added to each subset.
OR if we want recursive solution,
```
def foo(arr):
if len(arr) == 0:
return [[]]
else:
prev_subsets = foo(arr[:-1])
return prev_subsets + [a + [arr[-1]] for a in prev_subsets]
print(foo([1,2,3]))
```
honestly, it is not that the problem cannot be solved. If I am faced with this problem in real life like as a homework problem, I might get stuck for the first 10 minutes, and then I might put it down, do something else, maybe have lunch, and then I think of something, and then I try it, and yes, I was able to solve it the second time I thought about it, using the binary representation... so I can solve it... it is just that within that 20 minutes per interview question time frame, you might not show a solution like a straight line from point A to point B. So does that mean you are not good? I am sure many programmers, they might do something in the morning, and in the afternoon or the next day, they thought, hold on a second, there is a much better way! Does that mean they are not good, because they don't give the perfect solution in a 20 minute time frame?
my first thought is using dynamic programming, dp[n][ ]=dp[ n-1][ ]+(dp[ n-1][ ]+given_array[n])//plus in here means print
it's more straightforward for me.
I was struggling it using a BTS, at the end I came up with a mix (but basically, the magic in here is iterate the array recursively instead of using a loop function.
This is my solution
class SubSet{
constructor(content = []) {
this.content = content;
this.left = null;
this.right = null;
}
}
function helper(array, set, i) {
if (array.length === i) {
console.log(set.content);
}
else{
set.left = new SubSet(set.content.concat(array[i]));
helper(array, set.left, i + 1);
set.right = new SubSet(set.content);
helper(array, set.right, i + 1);
}
}
helper([1,2,3,4,5,6], new SubSet, 0);
The time complexity would be O(2^n) correct me if I am wrong
Incrementing a binary number to 2^n and following the 1s is easier. But I don't know if it's efficient.
Something similar like Anagram.
subsets = [];
function allSubsets(arr, currentSep = []) {
subsets.push(currentSep);
if(arr.length == 0) {
return;
}
for(var i = 0; i < arr.length; i++) {
debugger;
var ca = arr.slice(0,i).concat(arr.slice(i+1));
var cs = currentSep.concat(arr[i]);
allSubsets(ca,cs);
}
return subsets;
}
console.clear();
console.log(allSubsets([1,2,3]));