Отрицательные значения подмножества

Question

Мне было интересно, как работать с отрицательными значениями и отрицательной целью, прямо сейчас моя программа дает индекс из ошибок границ, когда отрицательные значения даются этим переменным. Мне нужно, чтобы моя функция hasSum работала с отрицательными значениями для этого проекта, я не могу просто считать положительным.

import java.util.Stack; 
import java.util.Scanner; 

public class subsetSum { 
    static Scanner input = new Scanner(System.in); 
    static { 
     System.out.print("Enter the target (T)" + "\n"); 
    } 

    /** Set a value for target sum */ 
    static int TARGET_SUM = input.nextInt(); //this is the target 

    /** Store the sum of current elements stored in stack */ 
    static int sumInStack = 0; 

    Stack<Integer> stack = new Stack<Integer>(); 

    public static void main(String[] args) { 

     //the size is S 
     System.out.println("\n" + "Enter the size of the set (S)"); 
     int values = input.nextInt(); //size = "values" 

     //value of each size entry 
     System.out.println("\n" + "Enter the value of each entry for S"); 

     int [] numbers = new int[values]; 

     for(int i = 0; i < values; i++) //for reading array 
     { 
      numbers[i] = input.nextInt();     
     } 

     if(hasSum(numbers, TARGET_SUM)){ 
      System.out.println("\n" + "Can: "); 
      subsetSum get = new subsetSum(); // encapsulation 
      get.populateSubset(numbers, 0, numbers.length); 
     }else{ 
      System.out.println("\n" + "Cannot"); 
     } 
    } 

    //method based on dynamic programming O(sum*length) 
    public static boolean hasSum(int [] array, int sum) 
    { 
     int i; 
     int len = array.length; 
     boolean[][] table = new boolean[sum + 1][len + 1]; //this has to be changed for negative 

     //If sum is zero; empty subset always has a sum 0; hence true 
     for(i = 0; i <= len; i++){ 
      table[0][i] = true; 
     } 

     //If set is empty; no way to find the subset with non zero sum; hence false 
     for(i = 1; i <= sum; i++){ 
      table[i][0] = false; 
     } 

     //calculate the table entries in terms of previous values 
     for(i = 1; i <= sum; i++) 
     { 
      for(int j = 1; j <= len; j++) 
      { 
       table[i][j] = table[i][j - 1]; 
       if(!table[i][j] && i >= array[j - 1]){ 
        table[i][j] = table[i - array[j - 1]][j - 1]; 
       } 
      } 
     }  
     return table[sum][len]; //this has to be changed for negative 
    } 

    public void populateSubset(int[] data, int fromIndex, int endIndex) { 
     /* 
     * Check if sum of elements stored in Stack is equal to the expected 
     * target sum. 
     * 
     * If so, call print method to print the candidate satisfied result. 
     */ 
     if (sumInStack >= TARGET_SUM) { 
      if (sumInStack == TARGET_SUM) { 
       print(stack); 
      } 
      // there is no need to continue when we have an answer 
      // because nothing we add from here on in will make it 
      // add to anything less than what we have... 
      return; 
     } 

     for (int currentIndex = fromIndex; currentIndex < endIndex; currentIndex++) { 
      if (sumInStack + data[currentIndex] <= TARGET_SUM) { 
       stack.push(data[currentIndex]); 
       sumInStack += data[currentIndex]; 
       /* 
       * Make the currentIndex +1, and then use recursion to proceed 
       * further. 
       */ 
       populateSubset(data, currentIndex + 1, endIndex); 
       sumInStack -= (Integer) stack.pop(); 
      } 
     } 
    } 

    /** 
    * Print satisfied result. i.e. 5 = 1, 4 
    */ 
    private void print(Stack<Integer> stack) { 
     StringBuilder sb = new StringBuilder(); 
     for (Integer i : stack) { 
      sb.append(i).append(","); 
     } 
     // .deleteCharAt(sb.length() - 1) 
     System.out.println(sb.deleteCharAt(sb.length() - 1).toString()); 
    } 
} 

Answer 1

Вы пытаетесь найти сумму подмножества или подмассива?
Если подмножества, то простая рекурсия может сделать трюк, например:

public static boolean hasSum(int [] array, int sum) 
{ 
    return hasSum(array, 0, 0, sum); 
} 

private static boolean hasSum(int[] array, int index, int currentSum, int targetSum) { 
    if (currentSum == targetSum) 
     return true; 
    if (index == array.length) 
     return false; 
    return hasSum(array, index + 1, currentSum + array[index], targetSum) || // this recursion branch includes current element 
      hasSum(array, index + 1, currentSum, targetSum); // this doesn't 
} 

Если вы пытаетесь найти подмассив, я хотел бы использовать prefix sums, например:

public static boolean hasSum(int [] array, int sum) 
{ 
    int[] prefixSums = new int[array.length]; 
    for (int i = 0; i < prefixSums.length; i++) { 
     prefixSums[i] = (i == 0) ? array[i] : array[i] + prefixSums[i - 1]; 
    } 

    for (int to = 0; to < prefixSums.length; to++) { 
     if (prefixSums[to] == sum) 
      return true; // interval [0 .. to] 
     for (int from = 0; from < to; from++) { 
      if (prefixSums[to] - prefixSums[from] == sum) 
       return true; // interval (from .. to] 
     } 
    } 
    return false; 
} 

BTW Я думаю, что чтение входных значений от Scanner внутри статического инициализатора - плохая идея, почему бы вам не переместить их на main()?