Python solution for sum of subsets using backtracking

By MOKSHITHA CHANDAMPETA

This tutorial helps you learn the backtracking approach for solving sum of subsets problem.

Problem statement : We are given 'n' distinct positive integers and a target_sum. We have to find the combinations of these numbers which exactly sum up to the target_sum value.

Example : Let n=5 and given positive integers are my_list={1,2,3,4,5}. Let the given target_sum=6.The subsets that produce the total of 6 are {1,5},{2,4} which is the output of our program. This is because 1+5=2+4=6.

Approach : We use backtracking approach. It is a recursive algorithm that uses brute force concept. The term backtracking implies that if the current solution is not suitable, then move a step back and try other solutions.

We make use of the below mentioned algorithm.

1. Start with an empty set.

2. Include the next element from list to set.

3. If the numbers in the set sum up to given target_sum, It is a solution set. 

4. If the set doesnot sum upto the target_sum or if we have reached the end of my_list, then backtrack the set until we find a solution set.

5. If we get a feasible solution, go to step 2.

6. If we have traversed all the elements and if no backtracking is possible, then stop without solution.

Variables & Declarations :

1. n stores the number of positive integers.

2. my_list stores the given numbers.

3. target_sum is the variable that stores the required sum given by user.

4. We use a solution vector x[] where for every element in my_list,

x[i]=1, If the element my_list[i] is included in the set and x[i]=0 otherwise.

5. total variable stores the sum of all elements in the given list.

6. s value stores the sum of all elements included in the subset.

7. rem stores the sum that has not been included.

State space tree :

Example:

n=6, my_list={5,10,12,13,15,18}, target_sum=30

The data in rectangular boxes denote values of s,k,rem.

A,B,C are the solution sets which include {5,10,15} , {5,12,13} , {12,18}

Bounding Conditions :

1. When a node that represents a subset whose sum equals the desired target_sum , terminate.

2. When a node that represents a subset whose sum exceeds the desired target_sum , backtrack. i.e., do not enter its subtrees, go back to parent node.

3. The variable rem gives you the sum of the numbers not yet considered. When you move to a right child, check if current subset sum s + rem >= target_sum. If not, backtrack.