text: 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
code: #include <stdio.h> NEW_LINE #include <stdlib.h> NEW_LINE #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 ++ ) { printf ( " % * d " , 5 , A [ i ] ) ; } printf ( " 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 = ( int * ) malloc ( size * sizeof ( int ) ) ; 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 ) ; printf ( " Nodes ▁ generated ▁ % d ▁ STRNEWLINE " , total_nodes ) ; return 0 ; }