In a given integer array finding subset with minimum elements that gives a sum.
For example in the given integer array
{110,13,21,31,64,12,6,7,99,10,23}
what are the subsets with minimum number of elements with sum 100. Following is the answer.
7 is the mimimum number of elements in a subset with sum 100
Subset:[31, 6, 7, 10, 12, 13, 21]
/*
* Author: Ashok Kumar Chava
*/
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class SubsetFinder {
public static void main(String s[]) {
int arr[]={110,13,21,31,64,12,6,7,99,10,23};
int k=100;
boolean found=false;
Arrays.sort(arr);
System.out.println("Input array after sorting:"+Arrays.toString(arr));
for(int i=1;i<arr.length;i++) {
ArrayList<Integer> subSet=SubsetFinder.subSetFinder(arr,i,k);
if(subSet!=null&&subSet.size()>0) {
System.out.println(i+ " is the mimimum number of elements in a subset with sum "+k);
System.out.println("Subset:"+subSet);
found=true;
break;
}
}
if(found!=true) {
System.out.println("There are no subsets that gives the sum "+k);
}
}
public static ArrayList<Integer> subSetFinder(int[] arr,int subSetSize, int sum) {
ArrayList<Integer> subList=new ArrayList<Integer>();
for(int i=0;i<arr.length;i++) {
subList=new ArrayList<Integer>();
subList.add(arr[i]);
int tempSum=arr[i];
int goBack=0;
if(tempSum==sum) {
return subList;
}
for(int j=0;j<arr.length&&subList.size()<subSetSize;j++) {
if(i!=j&&!subList.contains(arr[j])) {
tempSum=tempSum+arr[j];
subList.add(arr[j]);
}
if(tempSum==sum&&subList.size()==subSetSize) {
return subList;
}else if(tempSum!=sum&&subList.size()==subSetSize){
if(j%subSetSize==0) {
goBack=1;
}else {
goBack=j%subSetSize;
}
tempSum=tempSum-subList.get(subList.size()-(goBack));
subList.remove(subList.size()-(goBack));
}
}
}
return null;
}
}
For example in the given integer array
{110,13,21,31,64,12,6,7,99,10,23}
what are the subsets with minimum number of elements with sum 100. Following is the answer.
7 is the mimimum number of elements in a subset with sum 100
Subset:[31, 6, 7, 10, 12, 13, 21]
/*
* Author: Ashok Kumar Chava
*/
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class SubsetFinder {
public static void main(String s[]) {
int arr[]={110,13,21,31,64,12,6,7,99,10,23};
int k=100;
boolean found=false;
Arrays.sort(arr);
System.out.println("Input array after sorting:"+Arrays.toString(arr));
for(int i=1;i<arr.length;i++) {
ArrayList<Integer> subSet=SubsetFinder.subSetFinder(arr,i,k);
if(subSet!=null&&subSet.size()>0) {
System.out.println(i+ " is the mimimum number of elements in a subset with sum "+k);
System.out.println("Subset:"+subSet);
found=true;
break;
}
}
if(found!=true) {
System.out.println("There are no subsets that gives the sum "+k);
}
}
public static ArrayList<Integer> subSetFinder(int[] arr,int subSetSize, int sum) {
ArrayList<Integer> subList=new ArrayList<Integer>();
for(int i=0;i<arr.length;i++) {
subList=new ArrayList<Integer>();
subList.add(arr[i]);
int tempSum=arr[i];
int goBack=0;
if(tempSum==sum) {
return subList;
}
for(int j=0;j<arr.length&&subList.size()<subSetSize;j++) {
if(i!=j&&!subList.contains(arr[j])) {
tempSum=tempSum+arr[j];
subList.add(arr[j]);
}
if(tempSum==sum&&subList.size()==subSetSize) {
return subList;
}else if(tempSum!=sum&&subList.size()==subSetSize){
if(j%subSetSize==0) {
goBack=1;
}else {
goBack=j%subSetSize;
}
tempSum=tempSum-subList.get(subList.size()-(goBack));
subList.remove(subList.size()-(goBack));
}
}
}
return null;
}
}
