Subset Sum using Backtracking

Given a set (i.e. an array) of n distinct positive numbers, find a subset whose sum of elements is m.

Algorithm:

1. if index == array.length then
   1. return false
2. if array[index] == sum then
   1. return true
3. Iterate given array from index to array.length
   1. If array[i] > sum then
      1. don’t do anything take next element from array
   2. If array[i] == sum then
      1. return true
   3. Recursively call with with index +1 and sum – array[i]
   4. If last recursive call was success then
      1. return true
4. return false

Latest Source Code:
Github: SubsetSumUsingBacktracking.java

Output:

Sum subset for 5 : [3, 2]
Sum subset for 12 : [3, 2, 7]
Sum subset for 25 : [8, 10, 7]
Sum subset for 27 : [8, 2, 10, 7]
Subset not found for sum : 50
Sum subset for 20 : [8, 3, 2, 7]