# Divide and conquer for subset sum problem

I want my students (equivalent first-year college students) to work on algorithmic paradigms during a 2 hours practical programming session in OCaml.

I chose the subset sum problem since it can illustrate different paradigms:

Given an array $$A = [a_1, …, a_n]$$ of positive integer values, and a target $$T$$, is there a subset $$I \subset \{1, …, n\}$$ such that $$\sum\limits_{i\in I}a_i = T$$?

The algorithms I chose are:

• brute force testing is interesting because students must iterate through all subsets;
• dynamic programming algorithm is a classical pseudo-polynomial time algorithm;
• even a (non-optimal) greedy algorithm can be worked on if we consider the optimization version of the problem.

My question is about a divide-and-conquer algorithm. I couldn't find anything about it, so I thought about a way to do it:

1. If $$n = 1$$, answer $$a_1 = T \vee 0 = T$$, if $$n = 0$$, answer $$0 = T$$;
2. Otherwise, if for any $$t\in \{0, …, T\}$$, SSE has a solution for $$[a_1, …, a_{n/2}]$$ and $$t$$, and a solution for $$[a_{n/2+1}, …, a_n]$$ and $$T-t$$, answer True;
One of the problem is that the time complexity is quite ugly to compute. I found the relation: $$C(n, T) = \sum\limits_{t=0}^T\left(C\left(\frac{n}{2}, t\right) + C\left(\frac{n}{2}, T-t\right)\right) + \Theta(1)$$ I am not sure about the solution, but I found $$\Theta(n^{1+\log_2 T})$$ but it might be too difficult to compute (however, this is a practial session, so computing time complexity formulas is not the main objective). I finally found out that by memoizing, the algorithm can reach a time complexity of $$O(nT)$$, which is the same as the DP algorithm.