Category Archives: Recursion

Subset Sum using Backtracking

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]