In this post, we will learn how to solve the Subset Sum Problem using Backtracking.

What is Subset Sum Problem?

Given a set of elements and a sum value. We need to find the subset of the set elements which give the same sum as the sum value.

Example:

  • Set: {10, 7, 5, 18, 12, 20, 15}
  • Sum: 30
  • Output: [ {10, 5, 15}, {10, 20}, {7, 5, 18}, {18, 12} ]

There are two ways to solve the Subset Sum Problem

  1. Brute Force: Slow
  2. Backtracking: Fast

In the Bruteforce approach we usually try each combination starting from one, then two, then three and so on and we test for each combination for the required sum.

Using Backtracking we can reduce its time complexity to a great extent. Let’s see how.

Subset Sum Problem Solution using Backtracking Algorithm

The main idea is to add the number to the stack and track the sum of stack values.

Add a number to the stack, and check if the sum of all elements is equal to the sum. If yes then print the stack, else if the stack elements are less than the sum then repeat the step by adding the next element to the stack.

If the sum of stack elements exceeds the sum value then pop the last inserted element (top value) and repeat the process by adding the next available element.

In order to pop an element we need to backtrack, therefore we will use recursion.

The concept is almost similar to the solution of N Queen Problem using Backtracking.

Recommeded: What is Backtracking Algorithm?

Let’s see the algorithm to solve sum of subset problems in code.

Java

C++

Output

subset sum output 1

If you have any doubts or suggestion then comment below.

Leave a Reply

Close Menu