Subset Sum | Backtracking |  ; Prints subset found ; inputs s - set vector t - tuplet vector s_size - set size t_size - tuplet size so far sum - sum so far ite - nodes count target_sum - sum to be found ; We found subset ; Exclude previously added item and consider next candidate ; Generate nodes along the breadth ; Consider next level node ( along depth ) ; Wrapper to print subsets that sum to target_sum input is weights vector and target_sum ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ARRAYSIZE ( a )  (sizeof(a)) / (sizeof(a[0])) NEW_LINE #define mx  200 NEW_LINE static int total_nodes ; void printSubset ( int A [ ] , int size ) { for ( int i = 0 ; i < size ; i ++ ) { cout << A [ i ] << " ▁ " ; } cout << " STRNEWLINE ▁ " ; } void subset_sum ( int s [ ] , int t [ ] , int s_size , int t_size , int sum , int ite , int const target_sum ) { total_nodes ++ ; if ( target_sum == sum ) { printSubset ( t , t_size ) ; subset_sum ( s , t , s_size , t_size - 1 , sum - s [ ite ] , ite + 1 , target_sum ) ; return ; } else { for ( int i = ite ; i < s_size ; i ++ ) { t [ t_size ] = s [ i ] ; subset_sum ( s , t , s_size , t_size + 1 , sum + s [ i ] , i + 1 , target_sum ) ; } } } void generateSubsets ( int s [ ] , int size , int target_sum ) { int * tuplet_vector = new int [ mx ] ; subset_sum ( s , tuplet_vector , size , 0 , 0 , 0 , target_sum ) ; free ( tuplet_vector ) ; } int main ( ) { int weights [ ] = { 10 , 7 , 5 , 18 , 12 , 20 , 15 } ; int size = ARRAYSIZE ( weights ) ; generateSubsets ( weights , size , 35 ) ; cout << " Nodes ▁ generated ▁ " << total_nodes << " STRNEWLINE " ; return 0 ; }