Print All Possible Subsets with Sum equal to a given Number

by

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

public class PrintAllSubsetsToSum {
public void printSubSets(int N, int curr, String res){
if(curr==0){
System.out.println(res);
return;
}
for (int i = 1; i <=N ; i++) {
if(i<=curr){
printSubSets(N, curr–i, res+i);
}
}
}
public static void main(String[] args) {
int N = 4
new PrintAllSubsetsToSum().printSubSets(N,N,"");
}
}

view raw
PrintAllSubsetsToSum.java
hosted with ❤ by GitHub 

Output:
1111
112
121
13
211
22
31
4

Related Posts: