Question

Give an O(nt) algorithm for the following task. Input: A list of n positive integers $\mathbf{a}\mathbf{1}\mathbf{,}\mathbf{a}\mathbf{2}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}\mathbf{an}$; a positive integer $\mathbf{}\mathit{t}$. Question: Does some subset of the a_i’s add up to t? (You can use each a_i at most once.) (Hint: Look at subproblems of the form “does a subset of$\left\{a_1,a_2,...,a_i\right\}$ add up to ?”)

Short answer

The above problem can be solved in$\mathrm{O}\left(\mathrm{nt}\right)$ time by using dynamic programming paradigm. Here we will first define the recurrence relation and then solve each subproblem recursively.

Step-by-step solution

Dynamic programming approach.

In dynamic programming there are all possibilities and more time as compared to greedy programming. and the Dynamic programming approach always gives the accurate or correct answer. In dynamic programming have to compute only distinct function call because as soon as compute and store in one data structure so that after this reuse afterward if it is needed.

Defining Recurrence Relation

Let, $a_i\in a_1{a}_2\dots \dots .a_n$

Let the subproblem be$S\left(t-a_i\right).$ So at each subproblem,$S\left(t-a_i\right).$ which is the sum can be made from remaining value of ‘ $t’$.

We have following condition:

• If $\mathrm{S}\left(\mathrm{n}-1,\mathrm{t}-{\mathrm{a}}_{\mathrm{i}}\right)=\mathrm{True}$.

This means for any value of a_i, we can make sum up to ‘and it’s possible to obtain$\left(t-a_i\right)$from n-1 integers also. Thus,$S\left(n,t\right)$is True.

• If$S\left(n-1,t\right)=True$.

This means a_i cannot make value sum to ‘t’ and we can make value ‘t’ from$n-1$integers. Thus,

$S\left(n,t\right)$ is True.

• If above conditions are not true, then$S\left(n,t\right)$=False.

This shows that it is not possible to make sum value ‘ from using some integers.

So, the recursive equation is:

Where In dynamic programming have to compute only distinct function call because as soon as compute and store in one data structure so that after this reuse afterward if it is needed. And it is always solved in$O\left(nt\right)$ time by using dynamic programming paradigm. Here we will first define the recurrence relation and then solve each subproblem recursively.

$p\left[x,y,i\right]=p\left[x,y,i-1\right]\cup p\left[x-a,y,i-1\right]\cup p\left[x,y-a,i-1\right];fori,x,y>0$

Analysis of Above Recursive Relation in which each subproblem $S\left(n,t\right)$can be computed in $O\left(1\right)$time that is, in linear time. After computing $S\left(i,x\right)forin\left\{0\dots .n\right\}andxn\left\{0\dots .t\right\}.$Thus, the runtime is$O\left(nt\right).$