### 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:

- if index == array.length then
- return false

- if array[index] == sum then
- return true

- Iterate given array from index to array.length
- If array[i] > sum then
- don’t do anything take next element from array

- If array[i] == sum then
- return true

- Recursively call with with index +1 and sum – array[i]
- If last recursive call was success then
- return true

- If array[i] > sum then
- 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]