Arrays and sums

You are given an array of elements $A_1,A_2,A_3,...,A_N$. If you are considering index $i$, then you contain a set $S$ of all elements whose index is not equal to $i$. Your task is to find out if you can express $A_i$ as the sum of subsets of $S$.

For example, you have $8$ elements such as $1,2,3,4,5,6,7,8$ and you consider index $3$. Therefore, set $S$ is $\{1,2,4,5,6,7,8\}$ because you have to exclude the element at index $i$. The answer is Yes because you select subset $\{1,2\}$ and its sum is $3$. Suppose, if you consider index $8$, then set $S$ is $\{1,2,3,4,5,6,7\}$. The answer is Yes because you can select $\{1,2,5\}$, $[1,3,4\}$, $\{2,6\}$, or $\{3,5\}$.

Similarly, the answer for $i=2$ is No because set $S$ is $[1,3,4,5,6,7,8\}$ and there is no possible way such that you can select a subset and have sum $2$.

Note that you can select no more times than it occurs in set $S$.

You are given array $A$. For every index, your task is to determine if it is possible for index $i$ from $1$ to $N$.

Example:

Input: n=8, arr[]= { 1, 2, 3, 4, 5, 6, 7, 8 }
Output: 0 0 1 1 1 1 1 1 

Approach

Java

import java.util.Arrays;

public class ArraysSums {
    public static void main(String[] args) {

        int n = 8;
        int arr_org[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
        int arr[] = arr_org;
        Arrays.sort(arr);
        isSubsetSum(arr, n, 1000);

        for (int i = 0; i < n; i++) {
            if (subset[arr_org[i]][binarySearch(arr_org[i], n, arr)])
                System.out.print("1 ");
            else
                System.out.print("0 ");
        }

    }

    static boolean[][] subset;

    // binary search
    static int binarySearch(int i, int n, int[] arr) {

        int l = 0;
        int r = n;
        int mid = l + r / 2;
        while (l < r) {
            mid = (l + r) / 2;
            if (arr[mid] > i) {
                r = mid;
            } else {
                l = mid + 1;
            }

        }

        return l - 1;

    }

// calculate the sub set
    static boolean isSubsetSum(int set[], int n, int sum) {
        subset = new boolean[sum + 1][n + 1];

        for (int i = 0; i <= n; i++)
            subset[0][i] = true;

        for (int i = 1; i <= sum; i++)
            subset[i][0] = false;

        for (int i = 1; i <= sum; i++) {
            for (int j = 1; j <= n; j++) {
                subset[i][j] = subset[i][j - 1];
                if (i >= set[j - 1])
                    subset[i][j] = subset[i][j] || subset[i - set[j - 1]][j - 1];
            }
        }

        return subset[sum][n];

    }
}