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]

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;

}

}