Does this pseudocode for a non-recursive backtraking procedure for solving sum o

ID: 3685695 • Letter: D

Question

Does this pseudocode for a non-recursive backtraking procedure for solving sum of subsets problem look correct for the attached state-space tree?

Pseduocode of SumofSubsets(Non Recursive Backtracking Procedure)

Algorithm SumofSubsets(A[0:n-1, Sum, X[0:n])

Input: A[0:n-1] //array of positive integers

Sum //positive integer

X[0:n] //array of integers where X[1:n] stores fixed-tuple problem states

Output: Print all goal states, X[1],…..X[k] such that A[X[x]]+…+A[X[k]]= sum

K = k +1//Move to next level

For child = X[k-1]+1 to n-1

X[k] = child

Pathsum = pathsum+A[X[k]]

If Pathsum = sum then

Print(X[1],….X[k]) //goal state found so print out

PathSum = PathSum-A[X[k]]

Else

Sumofsubset(k)

End if

End for

End of SumofSubsets

1. All the elements of kth position are occured sequencially (one by one).

2. Each time x[k] is attached, through which one can easily check whether a solution has been found or not.

3. "For loop"is used which defines that no more values for x[k] are found and backtracking ends there.

This pseudocode for a non-recursive backtraking procedure for solving sum of subsets problem looks correct.

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.