Exponential subsets

You are given an integer array $A$ consisting of $N$ elements. Your task is to determine for every element if any of its powers can be expressed as the sum of any subset of array $A$.

Let $S$ be any subset of $A$.

${\displaystyle \sum _{i=1}^{S.size()}{S}_i=A[i{]}^K}$ where $K\ge 2$.

See sample for a better explanation.

If it is possible to do for any element, print 1. Otherwise, print 0.

Example:

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

Approach

Java

package com.java;

public class ExponentialSubsets {
    public static void main(String[] args) {
        int n = 8;
        // array
        int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
        // DP initialization
        boolean dp[][] = new boolean[n + 1][(n * n) + 1];
        for (int idx = 0; idx <= n; ++idx) {
            for (int sum = 0; sum < dp[idx].length; ++sum) {
                if (idx == 0 && sum == 0)
                    dp[idx][sum] = true;
                else if (idx == 0)
                    dp[idx][sum] = false;
                else {
                    dp[idx][sum] |= dp[idx - 1][sum];
                    if (sum >= arr[idx - 1]) {
                        dp[idx][sum] |= dp[idx - 1][sum - arr[idx - 1]];
                    }
                }
            }
        }

        for (int i = 0; i < n; ++i) {
            boolean ok = false;
            int curr = arr[i] * arr[i];
            if (curr == 1) {
                System.out.print(dp[n][curr] ? "1 " : "0 ");
                continue;
            }
            while (curr <= n * n) {
                if (dp[n][curr]) {
                    System.out.print(1 + " ");
                    ok = true;
                    break;
                }
                curr *= arr[i];
            }
            if (!ok)
                System.out.print(0 + " ");
        }
    }
}