# dynamic programming – Question concerning subset sum problem: split into 3 equal subsets

Task: Given an array $$arr(a_1, a_2, dots, a_n)$$ of integers, let $$A = sumlimits _{iin {1, 2, dots, n}}a_i$$. Determine whether it is possible to spit $$arr()$$ into 3 subsequences of equal sum, i.e. if $$s_1 =s_2 = s_3 =dfrac{A}{3}$$ where $$s_1 ,s_2 , s_3$$ denoted the splitted arrays.

My thoughts: I will first examine whether there exists some sequence of numbers that sums up to $$dfrac{A}{3}$$ via dp, then I will backtrack those numbers, “throw them out” (meaning I won’t consider them anymore), and proceed with the remaining numbers of the array. After doing this a second time I examine whether the numbers left sum up to $$dfrac{A}{3}$$ and return true if this is the case. Even though this sounds valid to me I somehow doubt the correctness of this.

Recurrence of DP: $$dp(i)(j) = dp(i-1)(j-a_j) text{ OR } dp(i-1)(j)$$

$$dp()$$ is a boolean array of dimension $$n timesdfrac{A}{3}$$.