Given a set of integers, is there a non-empty subset whose sum is zero? For example, given the set {-7, -3, -2, 5, 8}, the answer is yes because the subset {-3, -2, 5} sums to zero.
source Code
package com.dsacode.Algorithm.dynamic;
public class SubsetSum {
public static int[] Subsetsum(int []array, int inputSize, int targetValue){
int C[]=new int[targetValue+1];
C[0]=0;
for (int potentialSum = 1; potentialSum <= targetValue; potentialSum ++) {
int j;
for (j = 1; j <= inputSize; j++) {
int leftover=potentialSum-array[j];
if (leftover < 0)
continue;
if (C[leftover]==(-1))
continue;
if (C[leftover] < j)
break;
}
C[potentialSum]=( j <= inputSize) ? j : (-1);
}
return C;
}
public static void main(String[] args)
{
int inputSize=4;
int targetValue=4;
System.out.println("Size of input set: " + inputSize);
System.out.println("Target value: " + targetValue);
int S[]=new int[inputSize+1];
S[0]=0;
for (int i = 1;i <= inputSize; i++)
S[i]=i;
int []C = Subsetsum(S,inputSize,targetValue);
System.out.print(" input\tDynamicTable\n");
System.out.print("----------------------\n");
for (int i = 0; i <= targetValue; i++)
System.out.format("%3d \t %3d\n",i,C[i]);
System.out.println();
if (C[targetValue]==(-1))
System.out.print("No solution\n");
else
{
System.out.print("Solution\n");
System.out.print(" Input \t solution\n");
System.out.print("----------------------\n");
for (int i=targetValue;i>0;i-=S[C[i]])
System.out.format("%3d \t %3d\n",C[i],S[C[i]]);
}
}
}
