Print Subsets | Print PowerSets | Print all Subsequences
ฝัง
- เผยแพร่เมื่อ 5 ก.ย. 2024
- Print all subsets of a String.
Problem Description: practice.geeks...
Link: / adityaverma
Video Pdf Notes: / 38704785 .
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:
🖊️ : My Pen (Used in videos too): amzn.to/38fKSM1
👨🏻💻 : My Apple Macbook pro: amzn.to/3w8iZh6
💻 : My gaming laptop: amzn.to/3yjcn23
📱 : My Ipad: amzn.to/39yEMGS
✏️ : My Apple Pencil: amzn.to/3kMnKYf
🎧 : My Headphones: amzn.to/3kMOzM7
💺 : My Chair: amzn.to/385weqR
🛋 : My Table: amzn.to/3kMohtd
⏰ : My Clock: amzn.to/3slFUV3
🙋🏻♀️ : My girlfriend: amzn.to/3M6zLDK ¯\_(ツ)_/¯
PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.
Sir I was struggling to get some confidence to solve a new recursive problems and I literally watched many videos on recursion but never got the intuition but when I watched your recursion and dp... Playlist I am able to get the intuition for any new recursive problem. I can't explain how much gratitude I've for you but still thanks alot Sir :) Really admire your hard work
best programming content on youtube or on any platform.. nobody can match u... bhai recursion pdha rhe ho..next backtracking pdha dena..maza aa jaega
Backtracking kaha se padha hai bhai
@@PIYUSH-lz1zq backtracking kha se pdha bhai?
@@vivekgoswami1474backtracking kaha se padha bhai?
@@SohelDarwajkar backtracking ko bhi video daal d inhone check
@@vivekgoswami1474 are ik but I just wanted to continue that flow of que with 1 year gap lmaooo..See the first comment was 3 yrs back then second was 2,3rd was 1 and mine was -1 yr 😅..
I can say this with utmost confidence those insignificant amount of dislikes are from people who have not watched and performed previous videos of this playlist, otherwise this is the GOAT recursion course!
Backtracking kaha se padha hai bhai
And greedy
@@PIYUSH-lz1zq prateek narang dsa course on udemy
is this applicable for numbers ???
@@AdityaKumar-pp4xw is this ques applicable for numbers ???
Aditya, this is some different level of coding and so easy to understand especially for confusing topic like Recursion. First time I understand why people say to have "leap of faith" while solving recursion... Kudos to your efforts
both striver bhai and aditya bhai is dsa guru but guys seriously aditya bhai recursive playlist is more better than striver,btw striver recursion playlist also too good but aditya bhai recursion playist is just love....
Bhai adiya verma, bhagwan tujhe lambi umer de. first time aise vedio mili hai jisme itna sahi btaya hai
I could not find any other tutorial explaining intuition behind recursive tree solutions. This is the the only one. Thanks a ton!
is this applicable for numbers ???
You are doing great please go forward so that we can get more benefits and thanks for sharing your knowledge freely 🙌🙌😁
As you said in first video... Writing the code was really a cakewalk ! ❤️❤️
Haha thanks, do share with your friends and help the channel grow !!
Watched all videos of every playlist Till now and waiting for more..
Thankyou for making such an important channel
Bro please make BACKTRACKING videos.Your explanations are unanimously best on TH-cam.Thanks a lot man❤️
Thanks to humme bolna chahiye __/\__ I have had difficulty in understanding recursion but thanks to you, I am improving with every day.
code for c++
vectorm;
void solve(vector nums,vector op, vector &m) // m ko by address paas kiye as jo bhi changes m me ho wo vector wale fn me reflect ho and nums aur op ko pass by value kiye uska changes vector fn me reflect nahi hoga
{
if(nums.size()==0)
{
m.push_back(op);
return;
}
vectorop1=op;
vectorop2=op;
op2.push_back(nums[0]);
nums.erase(nums.begin()+0);
solve(nums,op1, m);
solve(nums,op2, m);
}
vector subsets(vector& nums) {
vector m;
vectorop;
solve(nums,op,m);
return m;
}
Nice
Java Code
private static void permutationFind(String input, String output) {
if(input.length()==0){
System.out.println(output);
return;
}
String out1 = output;
String out2 = output;
out2 += input.charAt(0);
input = input.substring(1);
permutationFind(input,out1);
permutationFind(input,out2);
}
Tnx bhai
out1 is redundant. You can remove it.
thanks bro
tysm bhai java mein code likh diya kro if possible
brother although the code works fine idk how.......but i have a serious doubt since op1 and op2 are two new strings created from op before every call to smaller input , i think we shud create a new String ip too because after the recursion call is over after ip.length == 0 how will the original string backtrack ??
Broooo the way you explain the solution is something else🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥
Python 3 Code
Time Complexity - O(2**N)
Space Complexity - O(1) [Excluded Auxilary Stack Space]
Code:
def generateSubsets(Input):
def helper(Op, In):
if(In == ""):
print(Op)
return
Op2 = Op
Op2 += In[0]
In = In[1:]
helper(Op, In)
helper(Op2, In)
helper("", Input)
Input = "abc"
generateSubsets(Input)
A very happy teachers day to the best teacher Aditya sir..you are the best teacher I ever had..you made recursion so easy I can't even thought.hope the almighty bless you with lots of happines and growth..😊😊
when he said "The guy who made dp/recursion easy". He really ment it!!!
is this applicable for numbers ???
Once again thanks Again. did saw the code in video just watched the tree part and design the code by myself. and did little tweak to avoid extra variable. and here it like you said cakewalk. thanks Aditya. posting the code also in java.
static void subSet(String op, String ip) {
if (ip.length() == 0) {
System.out.println(op);
return;
}
subSet(op, ip.substring(1, ip.length()));
subSet(op + ip.substring(0, 1), ip.substring(1, ip.length()));
}
AWesome
Did myself in 15 min! thanks bro!
Sachme vaiya apke vdo ki starting k music sei ek motivation milti he❤️
/*
* Subarray:
* 1: Contiguous
* 2: Order of appearence is maintained
* 3: Every subarray is a subset.
* 4: Every subarray is a subsequence
* 5:For an array/string of size n, we can have ( (n*(n+1))/2 + 1 ) Subarray in
* total i.e (n*(n+1))/2 non-empty subarray + 1 Empty subarray.
*
* Subsequence:
* 1: May or may not be contiguous
* 2: Order of appearence is maintained.
* 3: Derived by deleting some or none of the elements of the sequence without
* changing the order of
* the remaining elements.
* 4: Every subsequence is subset.
* 5: For a sequence/array/string of size n, we can have 2^n Subsequence in
* total i.e ((2^n)-1) non-empty sub-sequences + 1 Empty Subsequence.
*
* Subset:
* 1 : May or maynot be contiguous
* 2: Order of appearence may or may not be maintained.
* 3: Subsets and subsequence ae exactly same thing the only difference between
* them is that subsequence should maintain order of appearence of elements
* while subsets don't need to preserve order of appearence of elements
* for ex : {1,2} and {2,1} represent the same subset however while
* writing/listing the subsets of the sets you can either write {1,2} or {2,1}
* it doesnot matter but you can not list both at the same time
* since they are exactly the same thing.
*
* Ex: arr[]={1, 2, 3}
*
* Subarrays :
*
* [1]
* [1,2]
* [1, 2, 3]
* [2]
* [2,3]
* [3]
*
*
* Subsequences:
*
* []
* [1]
* [1, 2]
* [1, 3]
* [1, 2, 3]
* [2]
* [2, 3]
* [3]
*
* Subsets:
*
* []
* [1]
* [1, 2] or [2, 1]
* [1, 3] or [3, 1]
* [1, 2, 3] or [1, 3, 2] or [2, 3, 1] or [2, 1, 3] or [3, 1, 2] or [3, 2, 1]
* [2]
* [2, 3] or [3, 2]
* [3]
*/
//Iterative Approach
//Method 1 :
/*
For arr[] = {1, 2, 3}:
Intially: subsets :[[]]. (Add an empty subset)
Iteration 1: (arr[0]=1)
Pair 1 with all existing subsets i.e [1]
subsets: [[],[1]]
Iteration 2: (arr[1]=2)
Pair 2 with all existing subsets i.e [2] and [1, 2]
subsets: [[], [1], [2], [1, 2]].
Iteration 3: (arr[2]=3)
Pair 3 with all existing subsets i.e [3], [1, 3] , [2, 3] and [1, 2, 3]
subsets: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]].
*/
class Solution {
public List subsets(int[] arr) {
List subsets = new ArrayList();
subsets.add(new ArrayList()); // Start with the empty subset
for (int val : arr) {
int size = subsets.size();
for (int i = 0; i < size; i++) {
// Create a new subset from the existing subsets by adding the current number to
// it
List subset = new ArrayList(subsets.get(i));
subset.add(val);
subsets.add(subset);
}
}
return subsets;
}
}
// Method 2 : Bit Manipulation
/*
* For example : arr[] = {1, 2, 3, 4}; there are 16 (i.e 2^4) sub-sequences.
* If we carefully notice it is nothing but binary numbers from 0 to 15 which
* can be shown as below:
*
* 0000 {}
*
* 0001 {1}
*
* 0010 {2}
*
* 0011 {1, 2}
*
* 0100 {3}
*
* 0101 {1, 3}
*
* 0110 {2, 3}
*
* 0111 {1, 2, 3}
*
* 1000 {4}
*
* 1001 {1, 4}
*
* 1010 {1, 4}
*
* 1011 {1, 2, 4}
*
* 1100 {3, 4}
*
* 1101 {1, 3, 4}
*
* 1110 {2, 3, 4}
*
* 1111 {1, 2, 3, 4}
*
*
* Starting from right,whenever we encounter set bit(1) in a number at ith
* position the we print the element present at (i-1)th index in the array.
*/
// Intuitive Implementation
class Solution {
public List subsets(int[] arr) {
List subsets = new ArrayList();
// Total number of subsets is 2^n
int totalSubsets = 1
Best teacher for coding
at end of the video also mention time and space complexity..it will be useful for all of us.thank u
@Aditya Verma, Videos are very interesting and never forgot your teaching style... Thanks a lot keep going... Please upload some graph related videos.
Best Print all subset solution till now ❤️
is this applicable for numbers ???
Please Next Question -> Phone Keypad Combinations print.
thats backtracking bro, I will cover that in backtracking.
@@TheAdityaVerma Cool. Will wait for Backtracking Series.
@@TheAdityaVerma bro backtracking 13th se pehle acche se samjhado please
@@TheAdityaVerma Sir please next Playlist Backtracking pe bana dijiye🙏🙏.
@@TheAdityaVerma Backtracking and graph please
Please do a video on: Print all permutations of a string!
use backtracking
@@shivamagrawal3542 how
Thanks for the detailed explanation. Plesse could you make us undersatntd that what is the importance of the "return " statement and how missing it will cause a segmentation fault .Thanks
Basically ip length is zero right, ip is empty and if you wont write return that would mean recursion gonna be working again on the input, but this time its empty right? and in our code we are accessing ip[0] index which doesn't exist, which means it's a invalid memory access, and that would most probably leads to segmentation fault.
@@TheAdityaVerma Thanks Aditya, Got the point now..Thank you
bhaiya please add questions on binary trees which is totally dependent on recursion. Thanks
Can you please tell us the order of the upcoming topics like will you be teaching backtracking or graphs or trees. It will be helpful for us and will give us clarity.
recursion jaadu hai bhai .. Thanks a lot brother! you are the best! Please add graphs playlist as well
Problem: Product of Array Except Self
btw, Great content, thanks! :)
Bro you need to do preprocessing in this. Keep lets say a vector prod_ahead, where prod_ahead[I] = product of all elements from arr[I + 1] to last element, ( prod_ahead[n - 1] = 0 ) and then in another iteration, keep storing running_product such that running_prod at ith iteration is product of all elements left to i. then in the result vector, keep storing prod_ahead[I] * running_sum
for leetcode question [aditya verma method], array as input
void subset1(vector ip, vector op,vector& ans){
if(ip.size()==0){
ans.push_back(op);
return;
}
vector output1=op;
vector output2=op;
output2.push_back(ip[0]);
ip.erase(ip.begin()+0);
subset1(ip,output1,ans);
subset1(ip,output2,ans);
}
vector subsets(vector& nums) {
vector op={};
vector ans;
subset1(nums, op, ans);
return ans;
}
bhai feel dila de recursion ke , thanks a lot bhai
Hi brother, make a video on proper use of returns in recursion, most of the time I am out of clue when it comes to returns statement usage. That will be a great help. Thank you
i have same problem and commented the same in most of his videos but no reply
@@kanhaiyatulsyan7560 Basically ip length is zero right, ip is empty and if you wont write return that would mean recursion gonna be working again on the input, but this time its empty right? and in our code we are accessing ip[0] index which doesn't exist, which means it's a invalid memory access, and that would most probably leads to segmentation fault.
Glad to see your lecture brother👌
Take love from Bangladesh ❤🇧🇩
this is the best explanation I have ever seen!
@Aditya verma thanks a lot for removing the fear of recursion !! Before your videos, I used to avoid recursion wherever possible. Can you please suggest something on where to use the return statement generally in any question.
The above subset question can be written in the following way also
if(base condition) {
....
} else {
recursion call
induction
}
but we have written like this
if(base condition) {
...
return // so that we don't execute further operations
}
recursion call
induction
It makes the code more readable and nice.
Just remember that you can use return whenever you don't want to perform further operations in the function. How we use continue in the loop - so that further code is not executed and loop starts with next counter...
I hope I was able to explain.
instead of erase function we can just pass ip.substr(1); it returns the string remaining after the first element
Most liked youtuber of mine❤️
Keep the good work going ! Amazing videos. 👍😃
class Solution {
private:
// To solve this first draw Recursive tree then code it
void solve(vector& ans,int index,vector nums,vector output)
{
// base case
if(index>=nums.size())
{
ans.push_back(output);
//before returning we have to push the output in ans
return;
}
/* note pahle exclude ka recursion call krenge uske baad include krenge elements ko nahi toh pahle hi elements include ho jayenge toh ans me original array hi print hote rahega */
// exclude that element and Recursion call
solve(ans,index+1,nums,output);
// include that element
int element=nums[index];
output.push_back(element);
// Recursion call => Includded R.C
solve(ans,index+1,nums,output);
}
public:
vector subsets(vector& nums) {
vector ans;
vector output;
int index=0;
solve(ans,index,nums,output); // we create this function for recursive call bcz we have to pass each time (ans,index,nums,outpu)t and not returning anything only have to update the ans;
return ans;
}
};
// thanks me later
bas ek step tak chalakar dekh lenge IP-OP method main bhi? fir use hisab se likh denge code, baki apne aap kam kar jaega! pls correct me if I am wrong! Awesome way to explain man!
zindagi mein pheli bar smjh mein aaya hai
Hare Krishna!🙏🙏
Great Work
Thank you so much for this great playlist.
Thanks for such detailed explanation. One small suggestion from my side : "Try Using Dark theme Mode" a lot of the students like me watch your videos at night, and dark theme will be easy on the eyes.
Thanks you once again you're doing an amazing work :)
bhai mai normally comment nahi karta but thanks bro i will surely support you on pateron when i'm able to make enough money to support you
//Java Recursive functiion of this code
static void solve(String input,String output){
if(input.length() == 0){
System.out.println(output);
return;
}
//now take 1st char of input string
char ch = input.charAt(0);
//take char at 0th index of input string
solve(input.substring(1),output + ch);
//ignore char at 0th index of input string
solve(input.substring(1),output );
}
time complexity is o(2^n) .am i right ??
Wonderfully explained!! thank you.
Python Code (LC Subsets)
def subsets(A, output, result):
if len(A) == 0:
output.append(result)
return
L = result[:]
R = result[:]
R.append(A[0])
A = A[1:]
subsets(A, output, L)
subsets(A, output, R)
A = [1, 2, 3]
output = []
result = []
subsets(A, output, result)
print(output)
This code is having problem
@@saikatbanerjee7273
def solve(op,ip):
if len(ip)==0:
print(op, end =" ")
return
op1=op
op2=op
op2+=ip[0]
ip=ip[1:]
solve(op1,ip)
solve(op2,ip)
return
string="ab"
solve("",string)
Way better Sound quality in this one.
is can we able to do with array because we are not able to small the input with array?
Sir Your Video are really worthy and denote your true hardwork behind it. But Please try to release your series in an order from easy to hard. Do number them if necessary.
thanks a lot for explaining so beautifully
is this applicable for numbers ???
Thanks ! Awesome Explanation...
thank you.
Thanks for making recursion so easy!
Solution of subsets problem in javascript:-
function subsets(input,output){
if(input.length
Thank you Bhai, bohot hi easy understanding k sath problem samjadi aapne...! keep it up!
Here is my python code
def subsets(self, nums: List[int]) -> List[List[int]]:
self.res = []
op = []
ip = nums
self.solve(ip, op)
return self.res
def solve(self, ip, op):
if (not ip):
self.res.append(op)
return
op1 = op[:]
op2 = op[:]
op2.append(ip[0])
ip = ip[1:]
self.solve(ip, op1)
self.solve(ip, op2)
Can u explain meaning of op[:]
Bhaut mast smjhaya bhai!!
bhaiya please make video on Asymptotic notations and time complexity and space complexity
Python Implementation........
def subsets(self, nums: List[int]) -> List[List[int]]:
output = []
def helper_fun(start,temp,output):
output.append(temp)
for i in range(start,len(nums)):
helper_fun(i+1,temp + [nums[i]],output)
helper_fun(0, [],output)
return output
awesome explaination bro. thanks
#include
using namespace std;
void subsets(string input,string output){
if(input.size()==0){
cout
java - solution
public class PowerSet {
public static void main(String[] args) {
String ip = "abc";
String op = "";
subset(ip,op);
}
private static void subset(String ip, String op) {
if(ip.length()==0)
{
System.out.println(op);
return;
}
String op1 = op;
String op2 = op +ip.charAt(0);
ip = ip.substring(1);
subset(ip, op1);
subset(ip,op2);
}
}
Bhai aapka Flipkart and Nutanix interview experience share kab karoge.
bhaiya can you provide us with a list of practice questions of about 20-30 questions,it would be very much helpful ..as there are thousand of questions there on the internet
Thanks .. great explanation
how to memoize this. I am getting TLE on large test cases.
the same can be done with vector right? means to get all subsets of int array
is this applicable for numbers ???
@@PIYUSH-lz1zq its not working can u help wih soln
It does not work for array like ip: [1,2] and op: [[], [1], [2], [1,2]]
Please DP ki playlist pure Complete kardo.. LIS, Kadanes's wagera bache hain.. Plz next usse complete kardo..
What is the time complexity of above solution?
Great teacher
Bro,please please make a series on sliding window technique problems @Aditya Verma
use pointer.
You are doing great work. Can you pls take combination sum problem from leetcode as well.
bhaiya, kya aap Graph series bhi upload karoge?
aapka padhaya hua bohot acche se samajh mein aata hai, pls graphs bhi upload kardena
yaar apna bhai jis sequence m videos daal rha hai wo usne prioritise kre hue hain...he knows what is more important and trying to help us master those concepts first! So just stick with him! He'll eventually cover graphs.
Extremely thanks
how would you deal with negative number? it's taking -sign as a character...
If we call recursive function first on op1 and then op2 , it gives error . Why??
Thanks for this video
please put atleast subtitles sir, it will be helpful for us
bhaiya you are best
bhai ap kahi bhagwan nhi ho n ,glti se prithvi pe aa gye ho , kyoki itne ache se insan to sikha nhi skta hai
HEY, thank u for such a great explanation, only one doubt, can't we keep output as one variable instead of taking two different op1 and op2?
yes we can but for beginners taking two outputs will be good for better understanding.
is this applicable for numbers ???
@@PIYUSH-lz1zq input them as string or to take the last element use % and for first use // floor remember cpp // treated as comment so google floor
Bhai array pe DP kaise lagaye,uspe bhi vedio banao..Thanks in Advance.
Okayyy..
So, Smaller input will be same for all common nodes of a common generation?
Hona vi chahiye... its so obvious .. haina
Recursion OP!
i have done it using only IBH method . So my question is why do we should learn this method ?
Those names are just something I have given, behind the scenes everything works in the same way, IBH is nothing but a decision tree. (usually where we have one choice)
IBH or IP-OP method both have decision tree as their backbone :D
@@TheAdityaVerma Thanks for explanation and reply Bhaiyaa.
@@messi_codes can you please share your code?(IBH method)
I tried this approach by taking String input = "abc" this is working fine.. but i tried same in int array [1,2,3] then it is not giving correct output ( tried in java ).. can anyone help me please .. ? this is my code
public static void solve(ArrayList ip,ArrayList op ){
if(ip.size()==0){
System.out.println(op);
return;
}
ArrayList op1 = op;
ArrayList op2 = op;
op2.add(ip.get(0));
ip.remove(0);
solve(ip,op1);
solve(ip,op2);
}
Hey did you find the solution and what different approach we have to take for numbers?
You are manipulating in the original input and output , instead of creating a new instance for every new input and output. Please check this code:
--------------------------------------------------------------------------------------------------------------------------
void subset(List input,List output) {
if(input.size() == 0) {
System.out.println(output);
return;
}
List op1 = new ArrayList(output);
List op2 = new ArrayList(output);
op2.add(input.get(0));
input.remove(0);
subset(new ArrayList(input), op1);
subset(new ArrayList(input), op2);
}
--------------------------------------------------------------------------------------------------------------------------------
@@abulkasimlaskar Thank you bhai
Time complexity will be: (2^(N+1)) - 1
Can you please explain this?
Can we remove the last index instead of the first one ? if we remove last index then the time taken to shift the array is 0 essentially because we are just stripping of the last value.
Note - when we remove the first element from linked list time taken is O(1). But for Array implementations the time taken would be to shift the entire array :)
is this applicable for numbers ???
Jab jab input khali ho raha hai ..tab tab hame output mil raha hai , But base condition runs only once isn't it ? I am confused asf.
void solve(string s, string op, vector &v){
if(s.length()==0){
v.push_back(op);
return;
}
string op1=op;
string op2=op;
op2.push_back(s[0]);
s.erase(s.begin()+0);
solve(s,op1,v);
solve(s,op2,v);
return;
}
vector powerSet(string s)
{
//Your code here
string op="";
vector v;
solve(s,op,v);
return v;
}
is this applicable for numbers ???
bhai bhut pyaara
Gol mol recursive tree😍😍
Python Code :
def solve(ip,op):
if len(ip)==0:
print(op)
return
else:
op1=op
op2=op
op2=op2+ip[0]
ip=ip[1:]
solve(ip,op1)
solve(ip,op2)
return
s=input("Enter String: ").strip()
ip=s
op=''
solve(ip,op)
i have used ip.pop(0) in the place of ip=ip[1:] , but it gives only [],[1],[2] these outputs. can you explain why?