Sunday, March 01, 2020

Subset with minimum length from an integer array that gives a given sum

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;
    }
}