subroutine subset_sum_backtrack ( s, n, v, more, u, t ) !*****************************************************************************80 ! !! 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: ! ! 06 November 2022 ! ! Author: ! ! John Burkardt ! ! Parameters: ! ! Input, integer S, the desired sum. ! ! Input, integer N, the number of values. ! ! Input, integer V(N), the values. ! These must be nonnegative, and sorted in ascending order. ! Duplicate values are allowed. ! ! Input/output, logical MORE, should be set to FALSE before the first call. ! Thereafter, on output, MORE is TRUE if a solution is being returned, ! and FALSE if there are no more solutions. ! ! Input/output, integer U(N), should be set to 0 before the ! first call. On output with MORE TRUE, U indexes the selected entries ! of V that form a solution. ! ! Input/output, integer T, should be set to 0 before the first ! call. On output, if MORE is true, T is the highest index of the selected ! values, although this is of little interest to the user. ! implicit none integer n integer i logical more integer s integer su integer t integer told integer u(n) integer v(n) if ( .not. more ) then t = 0; u(1:n) = 0 else more = .false. u(t) = 0 told = t t = -1 do i = told - 1, 1, -1 if ( u(i) == 1 ) then t = i exit end if end do if ( t < 1 ) then return end if u(t) = 0 t = t + 1 u(t) = 1 end if do su = dot_product ( u, v ) if ( su < s .and. t < n ) then t = t + 1; u(t) = 1; else if ( su == s ) then more = .true. return else u(t) = 0 told = t t = -1 do i = told - 1, 1, -1 if ( u(i) == 1 ) then t = i exit end if end do if ( t < 1 ) then exit end if u(t) = 0 t = t + 1 u(t) = 1 end if end do return end