Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package demo;
- // In a given set of numbers, find all subsets that are equal to 0;
- public class HelloJava {
- public static void main(String[] args) {
- int[] numbers = {1, 0, -1, 2, 3, -2};
- int length = numbers.length;
- int sum = 0; // subset sum we look for
- int currentSum = 0;
- int counter = 0; // increment if subset found
- int combinations = (int) Math.pow(2, length) - 1;
- // go over all combinations from 00..1 => 11..1
- for(int i = 1; i < combinations; i++){
- String bin = Integer.toBinaryString(i);
- bin = padLeft(bin, '0', length);
- currentSum = 0;
- int digit = 0;
- // if char at bin is 1 get numbers[j]
- for(int j = 0; j < bin.length(); j++){
- digit = (bin.charAt(j) == '1') ? 1 : 0;
- if(digit == 1){
- currentSum += numbers[j];
- }
- }
- // compare & increment if necessary
- if(currentSum == sum){
- counter++;
- }
- }
- System.out.println("Subset Sums found: " + counter);
- }
- public static String padLeft(String str, char symbol, int length){
- int padding = length - str.length();
- if(padding > 0){
- for(int i = 0; i < padding; i++){
- str = symbol + str;
- }
- }
- return str;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement