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

    • I have checked it, program is working fine, could you tell me which input did you try and what was the output???

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

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

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

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

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

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

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

    Reply
  4. 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;
    }
    }
    }
    }

    Reply

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.