Advertisement
ivan_yosifov

Subset Sums Counter

Jun 5th, 2014
238
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.19 KB | None | 0 0
  1. package demo;
  2. // In a given set of numbers, find all subsets that are equal to 0;
  3. public class HelloJava {
  4.     public static void main(String[] args) {
  5.         int[] numbers = {1, 0, -1, 2, 3, -2};
  6.         int length = numbers.length;
  7.         int sum = 0; // subset sum we look for
  8.         int currentSum = 0;
  9.         int counter = 0; // increment if subset found
  10.        
  11.         int combinations = (int) Math.pow(2, length) - 1;
  12.  
  13.         // go over all combinations from 00..1 => 11..1
  14.         for(int i = 1; i < combinations; i++){
  15.             String bin = Integer.toBinaryString(i);
  16.             bin = padLeft(bin, '0', length);
  17.            
  18.             currentSum = 0;
  19.             int digit = 0;
  20.             // if char at bin is 1 get numbers[j]
  21.             for(int j = 0; j < bin.length(); j++){
  22.                 digit = (bin.charAt(j) == '1') ? 1 : 0;
  23.                 if(digit == 1){
  24.                     currentSum +=  numbers[j];
  25.                 }
  26.             }
  27.            
  28.             // compare & increment if necessary
  29.             if(currentSum == sum){
  30.                 counter++;
  31.             }          
  32.         }
  33.        
  34.         System.out.println("Subset Sums found: " + counter);
  35.     }
  36.    
  37.     public static String padLeft(String str, char symbol, int length){
  38.         int padding = length - str.length();
  39.        
  40.         if(padding > 0){
  41.             for(int i = 0; i < padding; i++){
  42.                 str = symbol + str;
  43.             }
  44.         }
  45.        
  46.         return str;
  47.     }
  48. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement