Sum of subsets
Mon Nov 18 2024 09:39:20 GMT+0000 (Coordinated Universal Time)
Saved by
@badram123
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
static boolean flag = false;
static void printSubsetSum(int i, int n, int[] set, int targetSum, List<Integer> subset) {
if (targetSum == 0) {
flag = true;
System.out.print("[ ");
for (int j = 0; j < subset.size(); j++) {
System.out.print(subset.get(j) + " ");
}
System.out.print("]");
return;
}
if (i == n) {
return;
}
printSubsetSum(i + 1, n, set, targetSum, subset);
if (set[i] <= targetSum) {
subset.add(set[i]);
printSubsetSum(i + 1, n, set, targetSum - set[i], subset);
subset.remove(subset.size() - 1);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter the number of elements in the set: ");
int n = sc.nextInt();
int[] set = new int[n];
System.out.println("Enter the elements of the set:");
for (int i = 0; i < n; i++) {
set[i] = sc.nextInt();
}
System.out.print("Enter the target sum: ");
int targetSum = sc.nextInt();
List<Integer> subset = new ArrayList<>();
System.out.println("Subsets with the given sum:");
printSubsetSum(0, n, set, targetSum, subset);
if (!flag) {
System.out.println("No subset with the given sum exists.");
}
}
}
content_copyCOPY
Comments