Breaking
Dynamic programming

# Subset Sum Problem

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]]);
}
}
}```

## Output

```Size of input set: 4
Target value: 4
Input   Dynamic Table
----------------------
0        0
1        1
2        2
3        2
4        3

Solution
Input  solution
----------------------
3        3
1        1```