Subset Sum | Backtracking |  ; prints subset found ; qsort compare function ; 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 sum ; constraint check ; Exclude previous added item and consider next candidate ; constraint check ; generate nodes along the breadth ; consider next level node ( along depth ) ; Wrapper that prints subsets that sum to target_sum ; sort the set ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ARRAYSIZE ( a )  (sizeof(a))/(sizeof(a[0])) NEW_LINE static int total_nodes ; void printSubset ( int A [ ] , int size ) { for ( int i = 0 ; i < size ; i ++ ) { cout << " ▁ " << A [ i ] ; } cout << " STRNEWLINE " ; } int comparator ( const void * pLhs , const void * pRhs ) { int * lhs = ( int * ) pLhs ; int * rhs = ( int * ) pRhs ; return * lhs > * rhs ; } 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 ) ; if ( ite + 1 < s_size && sum - s [ ite ] + s [ ite + 1 ] <= target_sum ) { subset_sum ( s , t , s_size , t_size - 1 , sum - s [ ite ] , ite + 1 , target_sum ) ; } return ; } else { if ( ite < s_size && sum + s [ ite ] <= target_sum ) { for ( int i = ite ; i < s_size ; i ++ ) { t [ t_size ] = s [ i ] ; if ( sum + s [ i ] <= target_sum ) { 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 = ( int * ) malloc ( size * sizeof ( int ) ) ; int total = 0 ; qsort ( s , size , sizeof ( int ) , & comparator ) ; for ( int i = 0 ; i < size ; i ++ ) { total += s [ i ] ; } if ( s [ 0 ] <= target_sum && total >= target_sum ) { subset_sum ( s , tuplet_vector , size , 0 , 0 , 0 , target_sum ) ; } free ( tuplet_vector ) ; } int main ( ) { int weights [ ] = { 15 , 22 , 14 , 26 , 32 , 9 , 16 , 8 } ; int target = 53 ; int size = ARRAYSIZE ( weights ) ; generateSubsets ( weights , size , target ) ; cout << " Nodes ▁ generated ▁ " << total_nodes ; return 0 ; }