Convert recursion to dynamic-CodePudding

i have a task: array of digits [8 1 2 8 2 10 4 5], need to identify if any elements of its can be half of it total sum. In example sum of elements is 40, half sum is 20. Elements can be 8,2,10 or 5,1,4,10 . Don't matter whats digits are, only true or false result. I check all possible sums of digits by recursion, and I confused how convert it to cycles

 private static boolean isExist(int[] data, int n, int sum) {
    if (sum == 0)
        return true;
    if (n <= 0)
        return false;
    if (data[n - 1] == sum)
        return true;
    if (sum < data[n - 1])
        return isExist(data, n - 1, sum);
    return isExist(data, n - 1, sum - data[n - 1]) || isExist(data, n - 1, sum);

}

CodePudding user response：

Make array A[] of length sum 1, make A[0]=1

For every element of value e: check in reverse direction (from the end of array to beginning) if A[i-e]==1, in this case make A[i]=1. (This denotes that sum i might be composed using current element and previously checked ones)

If A[sum] becomes 1, then needed subset does exist.

Working example in Python to demonstrate:

L = [7, 9, 3, 4, 6, 7]
S = sum(L) // 2
A = [0]*(S 1)
A[0] = 1
for e in L:
    for i in range(S, e-1, -1):  // scan backward
        if A[i-e]:
            A[i] = 1

print(A, A[-1] > 0)

>>  [1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]   True

L = [7, 9, 3, 4, 6, 13]
>> [1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0] False