Subset-Sum in Linear Time

Question 1

There are two things that make this problem possible:

The input can be truncated to size O(sqrt(n)). There are no negative inputs, so you can discard any numbers greater than 100*sqrt(n), and all inputs are distinct so we know there are at most 100*sqrt(n) inputs that matter.
The playing field has size O(sqrt(n)). Although there are O(2^sqrt(n)) ways to combine the O(sqrt(n)) inputs that matter, you don't have to care about combinations that either leave the 100*sqrt(n) range or redundantly hit a target you can already reach.

Basically, this problem screams dynamic programming with each input being checked against each part of the 'reached number' space somehow.

The solution ends up being a matter of ensuring numbers don't reach off of themselves (by scanning in the right direction), of only looking at each number once, and of giving ourselves enough information to reconstruct the solution afterwards.

Here's some C# code that should solve the problem in the given time:

int[] FindSubsetToImpliedTarget(int[] inputs) {
    var target = 100*(int)Math.Ceiling(Math.Sqrt(inputs.Count));

    // build up how-X-was-reached table
    var reached = new int?[target+1];
    reached[0] = 0; // the empty set reaches 0
    foreach (var e in inputs) {
        // we go backwards to avoid reaching off of ourselves
        for (var i = target; i >= e; i--) {
            if (reached[i-e].HasValue) {
                reached[i] = e;
            }
        }
    }

    // was target even reached?
    if (!reached[target].HasValue) return null;

    // build result by back-tracking via the logged reached values
    var result = new List<int>();
    for (var i = target; reached[i] != 0; i -= reached[i].Value) {
        result.Add(reached[i].Value);
    }
    return result.ToArray();
}

I haven't actually tested the above code, so beware typos and off-by-ones.

Question 2

With the typical DP algorithm for subset-sum problem will obtain O(N) time consuming algorithm. We use dp[i][k] (boolean) to indicate whether the first i items have a subset with sum k,the transition equation is:

dp[i][k] = (dp[i-1][k-v[i] || dp[i-1][k]),

it is O(NM) where N is the size of the set and M is the targeted sum. Since the elements are distinct and the sum must equal to 100*ceil(n^.5), we just need consider at most the first 100*ceil(n^.5) items, then we get N<=100*ceil(n^.5) and M = 100*ceil(n^.5).

The DP algorithm is O(N*M) = O(100*ceil(n^.5) * 100*ceil(n^.5)) = O(n).

Question 3

Ok following is a simple solution in O(n) time.

Since the required sum S is of the order of O(n^0.5), if we formulate an algorithm of complexity S^2, then we are good since our algorithm shall be of effective complexity O(n).

Iterate once over all the elements and check if the value is less than S or not. If it is then push it in a new array. This array shall contain a maximum of S elements (O(n^.5))
Sort this array in descending order in O(sqrt(n)*logn) time ( < O(n)). This is so because logn <= sqrt(n) for all natural numbers. https://math.stackexchange.com/questions/65793/how-to-prove-log-n-leq-sqrt-n-over-natural-numbers

Now this problem is a 1D knapsack problem with W = S and number of elements = S (upper bound).

Maximize the total weight of items and see if it equals S.

It can be solved using dynamic programming in linear time (linear wrt W ~ S).