Print All Possible Subsets with Sum equal to a given Number

by · June 8, 2015

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

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

Tags:

  • v110

    I tried the above code but not getting the correct output.

    • tutorialhorizon

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

      • v110

        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

        • tutorialhorizon

          I have posted the Recursion tree image for this problem your better understanding.Hope this will help.

        • Daniel

          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

          • tutorialhorizon

            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

          • Daniel

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

  • Kamal Chaya

    Is this the most efficient algorithm or is there a better way?

    Also what is the time complexity exactly?? Exponential?

    • tutorialhorizon

      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.

  • Abhishek Nancharla J

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

  • https://in.linkedin.com/in/ranjit-kumar-gouda-9452504b Ranjit Gouda

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

  • Santanu Sahoo

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

  • Atinesh Si

    Make it more clean by avoiding repetitions.

  • Ks

    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.

  • Ks

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

    • Ks

      Can someone help me with formatting. There’s some sort of auto formatting here while posting my solution.

Follow:

Select level

Beginner
Intermediate
Expert
%d bloggers like this: