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

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. Print All Possible Subsets with Sum equal to a given Number

Code

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

### 16 thoughts on “Print All Possible Subsets with Sum equal to a given Number”

1. 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.

• 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.

2. 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.

3. Hey! Thanks for the solution. I’m a bit confused as to why is this step necessary. ‘x = x.substring(0,x.length()-1);’

4. There should be one more condition for n< 0 or else it will go to infinite loop

5. 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 );
}
}

6. Make it more clean by avoiding repetitions.

7. 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.

8. 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;
}
}
}
}

• 