*--------------------------------------------------------------------------- function do_it() =test_1() =test_2() endfunc *--------------------------------------------------------------------------- function test_1() local i, InputArray[20, 1], OutputArray[1], n, j, k, x, SolutionArray[1], Cycles, Combinations local TimeStart, TimeEnd for i = 1 to alen(InputArray,1) InputArray[ i , 1] = i endfor InputArray[alen(InputArray,1)-1, 1] = 1000000 InputArray[alen(InputArray,1), 1] = InputArray[alen(InputArray,1)-1, 1] + 1 local NumberToFind NumberToFind = 0 for i = 1 to alen(InputArray,1) NumberToFind = NumberToFind + InputArray[i, 1] endfor ?'-----------Best case' TimeStart = seconds() ?CheckForSumIsResult(@InputArray, alen(InputArray,1), NumberToFind , 0,0,"") TimeEnd = seconds() - TimeStart ?'CheckForSumIsResult', NumberToFind, ttoc( { 00:00 } + TimeEnd , 2), TimeEnd TimeStart = seconds() n = MatchNumbers(NumberToFind, @InputArray, 0, FALSE, @OutputArray, @Cycles, @Combinations) TimeEnd = seconds() - TimeStart ?'MatchNumbers', NumberToFind, ttoc( { 00:00 } + TimeEnd , 2), TimeEnd for i = 1 to n ?'---------' x = strtran(OutputArray[ i, 2], ',', chr(0x0a) + chr(0x0d)) =alines(SolutionArray, x) for j = 1 to OutputArray[ i, 1] ?? InputArray[val(SolutionArray[j]), 1] endfor endfor ?'Solutions:', n, 'Tested', Cycles, '/', Combinations endfunc *--------------------------------------------------------------------------- function test_2() local i, InputArray[20, 1], OutputArray[1], n, j, k, x, SolutionArray[1], Cycles, Combinations local TimeStart, TimeEnd for i = 1 to alen(InputArray,1) InputArray[ i , 1] = i endfor InputArray[alen(InputArray,1)-1, 1] = 1000000 InputArray[alen(InputArray,1), 1] = InputArray[alen(InputArray,1)-1, 1] + 1 local NumberToFind NumberToFind = InputArray[alen(InputArray,1), 1]+InputArray[alen(InputArray,1)-1, 1] ?'------------------Worst case' TimeStart = seconds() ?CheckForSumIsResult(@InputArray, alen(InputArray,1), NumberToFind , 0,0,"") TimeEnd = seconds() - TimeStart ?'CheckForSumIsResult', NumberToFind, ttoc( { 00:00 } + TimeEnd , 2), TimeEnd TimeStart = seconds() n = MatchNumbers(NumberToFind, @InputArray, 0, FALSE, @OutputArray, @Cycles, @Combinations) TimeEnd = seconds() - TimeStart ?'MatchNumbers', NumberToFind, ttoc( { 00:00 } + TimeEnd , 2), TimeEnd for i = 1 to n ?'---------' x = strtran(OutputArray[ i, 2], ',', chr(0x0a) + chr(0x0d)) =alines(SolutionArray, x) for j = 1 to OutputArray[ i, 1] ?? InputArray[val(SolutionArray[j]), 1] endfor endfor ?'Solutions:', n, 'Tested', Cycles, '/', Combinations endfunc *--------------------------------------------------------------------------- Function MatchNumbers(SumToFind, InputArray, MaxDepth, MatchAll, OutputArray, Cycles, Combinations) local Depth Depth = alen(InputArray, 1) && MaxDepth tells us the max # of items contributing to the sum to find && zero = unlimited do case case empty(MaxDepth) MaxDepth = Depth otherwise MaxDepth = min(MaxDepth, Depth) endcase local Done Done = FALSE local i[MaxDepth], j, k, CurrentDepth, PreviousSum[MaxDepth] PreviousSum[1] = 0 local nSolutions, CurrentSum nSolutions = 0 Cycles = 0 Combinations = 0 for j = 1 to MaxDepth Combinations = Combinations + comb(Depth, j) endfor Local SumToFindPositive SumToFindPositive = (SumToFind >= 0) =iif(SumToFindPositive, asort(InputArray), asort(InputArray, 1, -1, 1)) for j = 1 to MaxDepth do case case Done exit otherwise CurrentDepth = 1 i[CurrentDepth] = 0 do while !Done and ( CurrentDepth > 0 ) do case case (i[CurrentDepth] < Depth + CurrentDepth - j) i[CurrentDepth] = i[CurrentDepth] + 1 do case case CurrentDepth = 1 CurrentSum = InputArray[ i[1], 1] otherwise PreviousSum[CurrentDepth] = PreviousSum[CurrentDepth-1] + InputArray[ i[CurrentDepth -1],1 ] CurrentSum = PreviousSum[CurrentDepth] + InputArray[ i[CurrentDepth], 1] endcase do case case iif(SumToFindPositive, CurrentSum > SumToFind, CurrentSum < SumToFind) && discard node CurrentDepth = CurrentDepth - 1 case (CurrentDepth < j) && not at full MaxDepth CurrentDepth = CurrentDepth + 1 i[CurrentDepth] = i[CurrentDepth-1] case CurrentSum = SumToFind && bingo nSolutions = nSolutions + 1 dime OutputArray[ nSolutions , 2] OutputArray[ nSolutions, 1] = j OutputArray[ nSolutions, 2] = transform(i[1]) for k = 2 to j OutputArray[ nSolutions, 2] = OutputArray[ nSolutions, 2] + ',' + transform(i[k]) endfor Done = !MatchAll Cycles = Cycles + 1 otherwise Cycles = Cycles + 1 endcase otherwise CurrentDepth = CurrentDepth - 1 endcase enddo endcase endfor return nSolutions endfunc *--------------------------------------------------------------------------- function comb(n,p) local r, i r = n-p+1 for i = r+1 to n r = r * i endfor for i = 2 to p r = r / i endfor return r endfunc *--------------------------------------------------------------------------- FUNCTION CheckForSumIsResult(aNumbers, nNumbers, nResultNumber, nTotal, nIndex, cCalc) LOCAL nT FOR nT = nIndex+1 TO nNumbers DO CASE CASE nTotal+aNumbers(nT,1) < nResultNumber =CheckForSumIsResult(@aNumbers, nNumbers, nResultNumber, nTotal+aNumbers(nT,1), nT, cCalc+"+"+ALLTRIM(STR(aNumbers[NT,1],10,2))) CASE nTotal+aNumbers(nT,1) = nResultNumber ? SUBSTR(cCalc+"+"+ALLTRIM(STR(aNumbers[nT,1],10,2)),2) OTHERWISE ** The sum is larger than the resultnumber ** There is no need to search further as all remaining numbers are even larger ** So exit here EXIT ENDCASE ENDFOR RETURN