Question

Course: Data Structures and Algorithms, in Java

Implement a function that reads numbers in from a file with one number per line and outputs all the possible sums that can be formed by subsets of the numbers. For instance, if the numbers in the file are 1 2 4, then the output would be 0, 1, 2, 4, 3, 5, 6, 7. Note that 0 is in the output because it uses none of the numbers, while 7 is the sum of all of the numbers.

// Return all sums that can be formed from subsets of elements in arr
public static ArrayList allSums( ArrayList arr ) { ... }

Answer 1

/******************************SumOfSubset.java*******************/

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class SumOfSubset {

   static ArrayList<Integer> allSum;

   public static void main(String[] args) {

       ArrayList<Integer> numbers = new ArrayList<>();
       File file = new File("number.txt");

       //read integers form file
       try {

           Scanner sc = new Scanner(file);
           // while loop till file has line
           while (sc.hasNextLine()) {

               numbers.add(Integer.parseInt(sc.nextLine()));
           }
           sc.close();
       } catch (FileNotFoundException e) {
           e.printStackTrace();
       }
       //calling method
       ArrayList<Integer> allSum = allSums(numbers);
       System.out.println(allSum);
   }

   public static ArrayList<Integer> allSums(ArrayList<Integer> numbers) {

       allSum = new ArrayList<>();
       //helper method
       getSum(numbers, 0, 0);
       //remove the duplicates
       Set<Integer> set = new HashSet<>(allSum);
       allSum.clear();
       allSum.addAll(set);
       return allSum;
   }

   private static void getSum(ArrayList<Integer> numbers, int starting, int sum) {

       if (numbers.size() == starting) {
           allSum.add(sum);
           return;
       }
       int value = sum + numbers.get(starting);
       getSum(numbers, starting + 1, value);
       getSum(numbers, starting + 1, sum);

   }

}
/*******************output*******************/

[0, 1, 2, 3, 4, 5, 6, 7]

[0, 2, 4, 6, 9, 11, 13, 15]

numbers.txt

Please let me know if you have any doubt or modify the answer, Thanks :)