Objective: Given a number N, Write an algorithm to print all possible subsets with Sum equal to N
This question has been asked in the Google for software engineer position.
Example:
N=4 1111 112 121 13 211 22 31 4
Approach:
This problem is quite similar to Print All Subsets of a given set.
- Loop through i=1 to N.
- Add i to the result and make a recursive call to (N-i).
- Base case: when n becomes 0
See the code for better explanation and recursion tree.
Code
Output: 1111 112 121 13 211 22 31 4
I tried the above code but not getting the correct output.
I have checked it, program is working fine, could you tell me which input did you try and what was the output???
I tried the same code in objective c with input n =4
my code is
– (void)findsubsets:(NSInteger)number value:(NSString*)value{
if (number == 0){
NSLog(@”%@”,value);
return;
}else{
for(int i = 1; i <= number; i++){
value = [NSString stringWithFormat:@"%@ %@", value, [[NSNumber numberWithInt:i] stringValue]];
[self findsubsets:number-1 value:value];
value = [value substringWithRange:NSMakeRange(0,value.length – 1)];
}
}
}
and i get
1 1 1 1
1 1 2 1
1 2 1 1
1 2 2 1
1 3 1 1
1 3 2 1
2 1 1 1
2 1 2 1
2 2 1 1
2 2 2 1
2 3 1 1
2 3 2 1
3 1 1 1
3 1 2 1
3 2 1 1
3 2 2 1
3 3 1 1
3 3 2 1
4 1 1 1
4 1 2 1
4 2 1 1
4 2 2 1
4 3 1 1
4 3 2 1
I have posted the Recursion tree image for this problem your better understanding.Hope this will help.
The problem with your code is this line: [self findsubsets:number-1 value:value];
You’re supposed to subtract “i” from number not the number 1.
Try that.
Also i’d love to connect and maybe do these together. I’m an iOS dev also, don’t find a lot of solutions in Obj-C. Would be great if we did some together.
Follow me on Twitter: @danielrakh
Its already number -i, which line exactly you are talking about in my code.
Yes we can do it together. will connect you in twitter
That was a reply to v110 not you : ) Yes. Feel free to message me on Twitter.
Is this the most efficient algorithm or is there a better way?
Also what is the time complexity exactly?? Exponential?
Yes the complexity is exponential. Since we are printing all the possible subsets which means all the numbers from 1 to n has two options, whether to be selected or not selected to get the result, , and position of number also matters for example 112, 121, 211 all are different solutions that is why it is exponential. Please suggest if you find better solution than this.
Hey! Thanks for the solution. I’m a bit confused as to why is this step necessary. ‘x = x.substring(0,x.length()-1);’
There should be one more condition for n< 0 or else it will go to infinite loop
This does not require any substring. Cheers !!!!!!!!
public static void print(int num,String op){
if(num == 0){
System.out.println(op);
}
for (int i = 1; i <= num; i++) {
print(num – i,op+i );
}
}
Make it more clean by avoiding repetitions.
Thanks for the solution. Could you please explain why do we need substring in this solution. I have tried to understand and ran code in IDE but still not clear.
Same solution with different implementation.
public static void subsets(int n, int sumSoFar, String res) {
//base case
if(sumSoFar == n) {
System.out.println(res);
} else {
for(int i =1; i<n; i++) {
if(sumSoFar+i <=n) {
//choose
res += i;
sumSoFar += i;
//explore
subsets(n, sumSoFar, res);
//un-choose
res = res.substring(0, res.length()-1);
sumSoFar -= i;
}
}
}
}
Can someone help me with formatting. There’s some sort of auto formatting here while posting my solution.