39 lines
1.2 KiB
Java
39 lines
1.2 KiB
Java
import java.util.*;
|
|
public class subsetSum{
|
|
static boolean found = false;
|
|
static int[] arr;
|
|
static int target;
|
|
static ArrayList<Integer> current= new ArrayList<>();
|
|
|
|
static void subset(int index, int sum, ArrayList<Integer> current){
|
|
if(sum==target){
|
|
found = true;
|
|
System.out.println("\nSubset found: "+current);
|
|
return;
|
|
}
|
|
if(arr.length == index || sum>target){
|
|
return;
|
|
}
|
|
current.add(arr[index]);
|
|
subset(index+1, sum+arr[index], current);
|
|
current.remove(current.size()-1);
|
|
subset(index+1, sum, current);
|
|
}
|
|
public static void main(String[] args){
|
|
Scanner sc= new Scanner(System.in);
|
|
System.out.println("\nEnter size of array: ");
|
|
int n = sc.nextInt();
|
|
arr = new int[n];
|
|
System.out.println("\nENter array elements: ");
|
|
for(int i=0;i<n;i++)
|
|
arr[i] = sc.nextInt();
|
|
System.out.print("Enter target: ");
|
|
target = sc.nextInt();
|
|
subset(0,0,new ArrayList<Integer>());
|
|
if(!found){
|
|
System.out.println("\nNo subset found");
|
|
}
|
|
sc.close();
|
|
}
|
|
}
|