Main72.cs

using System;

/// <summary>
/// Solves SPOJ Problem 8545 -- SubsetSum 
/// URL:http://www.spoj.com/problems/MAIN72/
/// </summary>
class Main72
{
    static bool isSubsetSumRec(int[] set, int n, int sum)
    {
        if (sum == 0)
            return true;

        if (sum != 0 && n == 0)
            return false;

        // ignoring this item since if we include, it will 
        // exceede sum. 
        if (set[n - 1] > sum)
            return isSubsetSumRec(set, n - 1, sum);

        return isSubsetSumRec(set, n - 1, sum - set[n - 1]) || isSubsetSumRec(set, n - 1, sum);

    }

    static void subsetSumRecursiveImpl()
    {
        Console.WriteLine("Computing subset sum using recusion");

        int[] set = { 2,3,2};
        int sum = 7;
        
        bool result1 = isSubsetSumRec(set, set.Length, sum);
        Console.WriteLine("isSubSetSum: " + result1);
    }
    
    static int computeSubsetSum(int[] set, int n, int sum) {
        bool[,] dp = new bool[n + 1, sum + 1];

        // base case1 : sum = 0 && i is non empty ----> true
        for (int i = 0; i <= n; i++) {
            dp[i, 0] = true;
        }

        // base case2: sum <> 0 and i=empty set --> false
        for (int j = 1; j <= sum; j++) {
            dp[0, j] = false;
        }

        // dp[i,j] is true if there is subset from 0 .. i-1 
        // with sum equal j or j - set[i]
        for (int i = 1; i < n+1; i++)
        {
            int s_i = set[i - 1];
            for (int j = 1; j < sum+1; j++)
            {
                if (j < s_i)
                    dp[i, j] = dp[i - 1, j];
                else
                    dp[i, j] = dp[i - 1, j] || dp[i - 1, j - s_i];
                    
            }
        }

        //// Uncomment following snippet to see the dp Table 
        //for (int i = 0; i < n+1; i++)
        //{
        //    for (int j = 0; j < sum+1; j++)
        //    {
        //        Console.Write(dp[i, j]?1:0);
        //        Console.Write(" ");
        //    }
        //    Console.WriteLine();
        //}

        int maxSum = 0;
        for (int j = 0; j < sum + 1; j++)
        {
            maxSum = maxSum+(dp[n, j] ? j : 0);
            
        }
        return maxSum;
    }

    static int solveCase() {
        int n = Int32.Parse(Console.ReadLine().Trim());
        int[] set = new int[n];
        int sum = 0;

        string[] numbers = Console.ReadLine().Trim().Split();
        for (int i = 0; i < n; i++)
        {
            set[i] = Int32.Parse(numbers[i]);
            sum += set[i];
        }

        return computeSubsetSum(set,n,sum);
    }
    
    static void Main(string[] args)
    {
        int noOfCases = System.Int32.Parse(Console.ReadLine());
        for (int caseNo = 1; caseNo <= noOfCases; caseNo++)
        {
            Console.WriteLine(solveCase());
        }
        
    }

}