Skip to content

Instantly share code, notes, and snippets.

@RitamChakraborty
Created August 7, 2019 17:37
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save RitamChakraborty/e39faa8d106690a08ec1942a064c3d0f to your computer and use it in GitHub Desktop.
Save RitamChakraborty/e39faa8d106690a08ec1942a064c3d0f to your computer and use it in GitHub Desktop.
Sum of Subsets problem implemented in java
import java.util.Arrays;
public class SumOfSubsets {
private static int required;
private static int[] arr;
private static int n;
private static void fun(int i, int[] sol, int sum, int remaining) {
if (remaining >= 0 && sum <= required) {
if (sum == required && remaining == 0) {
System.out.println(Arrays.toString(sol));
}
if (i < n) {
sol[i] = 1;
fun(i + 1, sol, sum + arr[i], remaining - arr[i]);
sol[i] = 0;
fun(i + 1, sol, sum, remaining - arr[i]);
}
}
}
public static void main(String[] args) {
arr = new int[]{1, 2, 3, 4, 5};
required = 10;
n = arr.length;
int sum = 0;
for (int a : arr) {
sum += a;
}
fun(0, new int[n], 0, sum);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment