Dynamic programming

Subset Sum Problem

Pinterest LinkedIn Tumblr

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

Algorithm Explanation

if subset is satisfying the constraint, print the subset
exclude the current element and consider next element
Generate the nodes of present level along breadth of tree and recur for next levels.

Time Complexity

Best CaseAverage CaseWorst Case
O(sum*n)

Reference

  1. http://mathworld.wolfram.com/SubsetSumProblem.html
  2. https://en.wikipedia.org/wiki/Subset_sum_problem
  3. https://eprint.iacr.org/2013/199.pdf
  4. http://www2.informatik.uni-halle.de/dasi/English/4.5.1.e.html

Write A Comment