0

I am cluelessly trying to solve this problem:

Let arr be an array of integers of length n (indexed from 1 to n).

Let M[s][i] be a matrix containing boolean values of, if there exist a subset of first i numbers of the array arr (arr[1], arr[2], ..., arr[i], ..., arr[n]), of which the sum is exactly s.

Find the recursive formula for the value of M[s][i] based on M[?][j], where j < i and arr contains j. You can assume that M[s][0] = 0.

How would I find this formula? I would be grateful for any help.

Community
  • 1
  • 1

1 Answers1

0

A simple recurrence formula based on your definition of M[s][i] would be:

M[s][i] = M[s][i-1] || M[s-arr[i]][i-1]

Explanation

  • If arr[i] is not included in the subset, M[s][i] is true if there exists a subset of first i-1 elements that has the sum exactly equal to s.
  • If arr[i] is included in the subset, then M[s][i] can only be true if there exists a subset of the first i - 1 elements that has a subset exactly equal to s - arr[i].

This problem is popularly called the Subset sum problem. It already has multiple answers here

Mukul Gupta
  • 2,310
  • 3
  • 24
  • 39
  • Thanks! So just to double check if I understand it correctly, regarding the second option. So you basically divided the problem into two subproblems, the first problem is 1, ... , i-1 and the second problem is just for i? –  Apr 26 '19 at 17:09
  • Yes. Basically, two subproblems, one in which the sum does not contain `arr[i]` and the second in which the sum contains `arr[i]`. – Mukul Gupta Apr 26 '19 at 17:11