# Print All Possible Subsets with Sum equal to a given Number

Objec­tive: Given a num­ber N, Write an algo­rithm to print all pos­si­ble sub­sets with Sum equal to N

In this prob­lem you will see the power of recur­sion. This ques­tion has been asked in the Google for soft­ware engi­neer position.

Exam­ple:

```N=4

1111
112
121
13
211
22
31
4
```

Approach:

This prob­lem is quite sim­i­lar to Print All Sub­sets of a given set.

• Loop through i=1 to N.
• Add i to the result and make a recur­sive call to (N-i).
• Base case: when n becomes 0

See the code for bet­ter expla­na­tion and recur­sion tree.

Print-All-Possible-Subsets-with-Sum-equal-to-a-given-Number

Code

```Output:
1111
112
121
13
211
22
31
4```

#### You may also like...

• v110

I tried the above code but not get­ting the cor­rect output.

• tuto­ri­al­hori­zon

I have checked it, pro­gram is work­ing fine, could you tell me which input did you try and what was the output???

• v110

I tried the same code in objec­tive c with input n =4
my code is

- (void)findsubsets:(NSInteger)number value:(NSString*)value{

if (num­ber == 0){

NSLog(@[email protected],value);

return;

}else{

for(int i = 1; i <= num­ber; i++){

value = [NSString stringWithFormat:@”%@ [email protected], value, [[NSNum­ber 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

• tuto­ri­al­hori­zon

I have posted the Recur­sion tree image for this prob­lem your bet­ter understanding.Hope this will help.

• Daniel

The prob­lem with your code is this line: [self findsubsets:number-1 value:value];

You’re sup­posed to sub­tract “i” from num­ber not the num­ber 1.
Try that.

Also i’d love to con­nect and maybe do these together. I’m an iOS dev also, don’t find a lot of solu­tions in Obj-C. Would be great if we did some together.

Fol­low me on Twit­ter: @danielrakh

• tuto­ri­al­hori­zon

Its already num­ber –i, which line exactly you are talk­ing about in my code.

Yes we can do it together. will con­nect you in twitter

• Daniel

That was a reply to v110 not you : ) Yes. Feel free to mes­sage me on Twitter.

• Kamal Chaya

Is this the most effi­cient algo­rithm or is there a bet­ter way?

Also what is the time com­plex­ity exactly?? Exponential?

• tuto­ri­al­hori­zon

Yes the com­plex­ity is expo­nen­tial. Since we are print­ing all the pos­si­ble sub­sets which means all the num­bers from 1 to n has two options, whether to be selected or not selected to get the result, , and posi­tion of num­ber also mat­ters for exam­ple 112, 121, 211 all are dif­fer­ent solu­tions that is why it is expo­nen­tial. Please sug­gest if you find bet­ter solu­tion than this.

• Abhishek Nan­charla J

Hey! Thanks for the solu­tion. I’m a bit con­fused as to why is this step nec­es­sary. ‘x = x.substring(0,x.length()-1);’

There should be one more con­di­tion for n< 0 or else it will go to infi­nite loop

• San­tanu Sahoo

This does not require any sub­string. Cheers !!!!!!!!

pub­lic sta­tic 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 );
}
}

• Ati­nesh Si

Make it more clean by avoid­ing repetitions.