Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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

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(@”%@”,value);

        return;

        }else{

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

        value = [NSString stringWithFormat:@”%@ %@”, 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);’

  • https://in.linkedin.com/in/ranjit-kumar-gouda-9452504b Ran­jit Gouda

    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.

  • Ks

    Thanks for the solu­tion. Could you please explain why do we need sub­string in this solu­tion. I have tried to under­stand and ran code in IDE but still not clear.

  • Ks

    Same solu­tion with dif­fer­ent implementation.

    pub­lic sta­tic void subsets(int n, int sum­So­Far, 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;
    sum­So­Far += i;

    //explore
    subsets(n, sum­So­Far, res);

    //un-choose
    res = res.substring(0, res.length()-1);
    sum­So­Far -= i;
    }
    }
    }
    }

    • Ks

      Can some­one help me with for­mat­ting. There’s some sort of auto for­mat­ting here while post­ing my solution.