Subset Sum (DP)

README.txt

This problem was asked by Google.

Given a list of integers S and a target number k, 
write a function that returns a subset of S that adds up to k.
If such a subset cannot be made, then return null.

Integers can appear more than once in the list. You may assume all numbers in the list are positive.

For example, given S = [12, 1, 61, 5, 9, 2] and k = 24, return [12, 9, 2, 1] since it sums up to 24.

Program.cs

class Program
{
    static int[] s;
    static int k;
    static Point[,] points;
    
    static void Main(string[] args)
    {
        k = 24;
        s = new int[] { 12, 1, 61, 5, 9, 2 };
        if (SubsetSum())
        {
            PrintPath(); // 2 + 9 + 1 + 12 = 24
        }
    }

    static bool SubsetSum()
    {
        int k = Program.k;
        int n = Program.s.Length;
        bool[,] dp = new bool[k + 1, n + 1];
        points = new Point[k + 1, n + 1];
        for (int j = 0; j <= n; j++)
        {
            dp[0, j] = true;
        }
        for (int i = 1; i <= k; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (i >= s[j - 1])
                {
                    dp[i, j] = dp[i - s[j - 1], j - 1];
                    if (dp[i, j])
                    {
                        points[i, j] = new Point(i - s[j - 1], j - 1);
                    }
                }
                if (!dp[i, j])
                {
                    dp[i, j] = dp[i, j - 1];
                    if (dp[i, j])
                    {
                        points[i, j] = new Point(i, j - 1);
                    }
                }
            }
        }
        return dp[k, n];
    }

    private static void PrintPath()
    {
        int k = Program.k;
        int n = Program.s.Length;
        Point p = points[k, n];
        int x = k;
        List<int> indices = new List<int>();
        while (p != null)
        {
            if (p.I != x)
            {
                indices.Add(p.J);
            }
            x = p.I;
            p = points[p.I, p.J];
        }
        Console.WriteLine(string.Join(" + ", indices
            .Select(x => s[x])) + $" = {k}");
    }
}

class Point
{
    public Point(int i, int j)
    {
        I = i;
        J = j;
    }

    public int I { get; private set; }
    public int J { get; private set; }

    public override string ToString()
    {
        return $"({I}, {J}";
    }
}