# include # include # include # include "subset_sum_backtrack.h" /******************************************************************************/ void subset_sum_backtrack ( int s, int n, int v[], bool *more, int u[], int *t ) /******************************************************************************/ /* Purpose: subset_sum_backtrack() seeks, one at a time, subsets of V that sum to S. Licensing: This code is distributed under the MIT license. Modified: 05 November 2022 Author: John Burkardt Input: int S, the desired sum. int N, the number of values. int V[N], the values. These must be nonnegative, and sorted in ascending order. Duplicate values are allowed. bool *MORE, should be set to FALSE before the first call. int U[N], should be set to 0 before the first call. int *T, should be set to -1 before the first call. Output: bool *MORE: MORE is TRUE if a solution is being returned, and FALSE if there are no more solutions. int U[N]: if MORE is TRUE, U indexes the selected entries of V that form a solution. int *T: if MORE is true, T is the highest index of the selected values, although this is of little interest to the user. */ { int i; int su; int told; if ( ! *more ) { *t = -1; for ( i = 0; i < n; i++ ) { u[i] = 0; } } else { *more = false; u[*t] = 0; /* Backup to previous 1. */ told = *t; *t = -1; for ( i = told - 1; 0 <= i; i-- ) { if ( u[i] == 1 ) { *t = i; break; } } if ( *t < 0 ) { return; } u[*t] = 0; *t = *t + 1; u[*t] = 1; } while ( true ) { su = 0; for ( i = 0; i < n; i++ ) { su = su + u[i] * v[i]; } if ( su < s && *t < n - 1 ) { *t = *t + 1; u[*t] = 1; } else { if ( su == s ) { *more = true; return; } u[*t] = 0; /* Backup to previous 1. */ told = *t; *t = -1; for ( i = told - 1; 0 <= i; i-- ) { if ( u[i] == 1 ) { *t = i; break; } } if ( *t < 0 ) { break; } u[*t] = 0; *t = *t + 1; u[*t] = 1; } } return; }