Subset Sum Problem using Backtracking
Given a set[] of non-negative integers and a value sum, the task is to print the subset of the given set whose sum is equal to the given sum.
Examples:
Input: set[] = {1,2,1}, sum = 3
Output: [1,2],[2,1]
Explanation: There are subsets [1,2],[2,1] with sum 3.Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 30
Output: []
Explanation: There is no subset that add up to 30.
Recommended: Please solve it on “PRACTICE ” first, before moving on to the solution.
Subset Sum Problem using Backtracking
Subset sum can also be thought of as a special case of the 0–1 Knapsack problem. For each item, there are two possibilities:
- Include the current element in the subset and recur for the remaining elements with the remaining Sum.
- Exclude the current element from the subset and recur for the remaining elements.
Finally, if Sum becomes 0 then print the elements of current subset. The recursion’s base case would be when no items are left, or the sum becomes negative, then simply return.
Implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; // Print all subsets if there is atleast one subset of set[] // with sum equal to given sum bool flag = 0; void PrintSubsetSum( int i, int n, int set[], int targetSum, vector< int >& subset) { // targetSum is zero then there exist a // subset. if (targetSum == 0) { // Prints valid subset flag = 1; cout << "[ " ; for ( int i = 0; i < subset.size(); i++) { cout << subset[i] << " " ; } cout << "]" ; return ; } if (i == n) { // return if we have reached at the end of the array return ; } // Not considering current element PrintSubsetSum(i + 1, n, set, targetSum, subset); // consider current element if it is less than or equal // to targetSum if (set[i] <= targetSum) { // push the current element in subset subset.push_back(set[i]); // Recursive call for consider current element PrintSubsetSum(i + 1, n, set, targetSum - set[i], subset); // pop-back element after recursive call to restore // subsets original configuration subset.pop_back(); } } // Driver code int main() { // Test case 1 int set[] = { 1, 2, 1 }; int sum = 3; int n = sizeof (set) / sizeof (set[0]); vector< int > subset; cout << "Output 1:" << endl; PrintSubsetSum(0, n, set, sum, subset); cout << endl; flag = 0; // Test case 2 int set2[] = { 3, 34, 4, 12, 5, 2 }; int sum2 = 30; int n2 = sizeof (set) / sizeof (set[0]); vector< int > subset2; cout << "Output 2:" << endl; PrintSubsetSum(0, n2, set2, sum2, subset2); if (!flag) { cout << "There is no such subset" ; } return 0; } // This code is contributed by Hem Kishan |
Java
import java.util.ArrayList; import java.util.List; public class SubsetSum { // Flag to check if there exists a subset with the given // sum static boolean flag = false ; // Print all subsets if there is at least one subset of // set[] with the sum equal to the given sum static void printSubsetSum( int i, int n, int [] set, int targetSum, List<Integer> subset) { // If targetSum is zero, then there exists a subset. if (targetSum == 0 ) { // Prints a valid subset flag = true ; System.out.print( "[ " ); for ( int j = 0 ; j < subset.size(); j++) { System.out.print(subset.get(j) + " " ); } System.out.print( "]" ); return ; } if (i == n) { // Return if we have reached the end of the // array return ; } // Not considering the current element printSubsetSum(i + 1 , n, set, targetSum, subset); // Consider the current element if it is less than // or equal to the targetSum if (set[i] <= targetSum) { // Push the current element in the subset subset.add(set[i]); // Recursive call for considering the current // element printSubsetSum(i + 1 , n, set, targetSum - set[i], subset); // Pop-back element after the recursive call to // restore the subset's original configuration subset.remove(subset.size() - 1 ); } } // Driver code public static void main(String[] args) { // Test case 1 int [] set1 = { 1 , 2 , 1 }; int sum1 = 3 ; int n1 = set1.length; List<Integer> subset1 = new ArrayList<>(); System.out.println( "Output 1:" ); printSubsetSum( 0 , n1, set1, sum1, subset1); System.out.println(); flag = false ; // Test case 2 int [] set2 = { 3 , 34 , 4 , 12 , 5 , 2 }; int sum2 = 30 ; int n2 = set2.length; List<Integer> subset2 = new ArrayList<>(); System.out.println( "Output 2:" ); printSubsetSum( 0 , n2, set2, sum2, subset2); if (!flag) { System.out.println( "There is no such subset" ); } } } |
Python3
# Print all subsets if there is at least one subset of set[] # with a sum equal to the given sum flag = False def print_subset_sum(i, n, _set, target_sum, subset): global flag # If targetSum is zero, then there exists a subset if target_sum = = 0 : # Prints valid subset flag = True print ( "[" , end = " " ) for element in subset: print (element, end = " " ) print ( "]" , end = " " ) return if i = = n: # Return if we have reached the end of the array return # Not considering the current element print_subset_sum(i + 1 , n, _set, target_sum, subset) # Consider the current element if it is less than or equal to targetSum if _set[i] < = target_sum: # Push the current element into the subset subset.append(_set[i]) # Recursive call for considering the current element print_subset_sum(i + 1 , n, _set, target_sum - _set[i], subset) # Remove the last element after recursive call to restore subset's original configuration subset.pop() # Driver code if __name__ = = "__main__" : # Test case 1 set_1 = [ 1 , 2 , 1 ] sum_1 = 3 n_1 = len (set_1) subset_1 = [] print ( "Output 1:" ) print_subset_sum( 0 , n_1, set_1, sum_1, subset_1) print () flag = False # Test case 2 set_2 = [ 3 , 34 , 4 , 12 , 5 , 2 ] sum_2 = 30 n_2 = len (set_2) subset_2 = [] print ( "Output 2:" ) print_subset_sum( 0 , n_2, set_2, sum_2, subset_2) if not flag: print ( "There is no such subset" ) |
C#
using System; using System.Collections.Generic; class Program { // Print all subsets if there is at least one subset of // set[] with a sum equal to the given sum static bool flag = false ; static void PrintSubsetSum( int i, int n, int [] set , int targetSum, List< int > subset) { // If targetSum is zero, then there exists a subset. if (targetSum == 0) { // Prints the valid subset flag = true ; Console.Write( "[ " ); foreach ( var item in subset) { Console.Write(item + " " ); } Console.Write( "]" ); return ; } if (i == n) { // Return if we have reached the end of the // array return ; } // Not considering the current element PrintSubsetSum(i + 1, n, set , targetSum, subset); // Consider the current element if it is less than // or equal to targetSum if ( set [i] <= targetSum) { // Push the current element into the subset subset.Add( set [i]); // Recursive call to consider the current // element PrintSubsetSum(i + 1, n, set , targetSum - set [i], subset); // Remove the last element to restore the // subset's original configuration subset.RemoveAt(subset.Count - 1); } } // Driver code static void Main() { // Test case 1 int [] set = { 1, 2, 1 }; int sum = 3; int n = set .Length; List< int > subset = new List< int >(); Console.WriteLine( "Output 1:" ); PrintSubsetSum(0, n, set , sum, subset); Console.WriteLine(); flag = false ; // Test case 2 int [] set2 = { 3, 34, 4, 12, 5, 2 }; int sum2 = 30; int n2 = set2.Length; List< int > subset2 = new List< int >(); Console.WriteLine( "Output 2:" ); PrintSubsetSum(0, n2, set2, sum2, subset2); if (!flag) { Console.WriteLine( "There is no such subset." ); } } } |
Javascript
// Function to print all subsets if there is at least one subset of set[] // with sum equal to the given sum let flag = false ; function printSubsetSum(i, n, set, targetSum, subset) { // If targetSum is zero, there exists a valid subset if (targetSum === 0) { // Print valid subset flag = true ; console.log( "[ " + subset.join( " " ) + " ]" ); return ; } if (i === n) { // Return if we have reached the end of the array return ; } // Not considering the current element printSubsetSum(i + 1, n, set, targetSum, subset); // Consider the current element if it is less than or equal to targetSum if (set[i] <= targetSum) { // Push the current element in the subset subset.push(set[i]); // Recursive call for considering the current element printSubsetSum(i + 1, n, set, targetSum - set[i], subset); // Pop-back element after the recursive call to restore subset's original configuration subset.pop(); } } // Driver code // Test case 1 const set1 = [1, 2, 1]; const sum1 = 3; const n1 = set1.length; const subset1 = []; console.log( "Output 1:" ); printSubsetSum(0, n1, set1, sum1, subset1); console.log( "" ); // Reset the flag flag = false ; // Test case 2 const set2 = [3, 34, 4, 12, 5, 2]; const sum2 = 30; const n2 = set2.length; const subset2 = []; console.log( "Output 2:" ); printSubsetSum(0, n2, set2, sum2, subset2); if (!flag) { console.log( "There is no such subset" ); } |
Output 1:
[ 2 1 ][ 1 2 ]
Output 2:
There is no such subset
Complexity analysis:
- Time Complexity: O(2n) The above solution may try all subsets of the given set in the worst case. Therefore time complexity of the above solution is exponential.
- Auxiliary Space: O(n) where n is recursion stack space.
Contact Us