Find all ways to sum given number (with repetitions allowed) from given set

If you're willing to excuse the fancy linq tricks, you might find this C# solution useful. Fortunately linq reads kind of like english. The idea is to build up the solutions as k starts from 0 and increments until it reaches its correct value. Each value of k builds on the previous solutions. One thing you have to watch for though is to ensure that the new "ways" you're finding are not re-orderings of others. I solved that by only counting them as valid if they're sorted. (which was only a single comparison)

void Main() {
    foreach (int[] way in GetSumWays(new[] {1, 2}, 6)) {
        Console.WriteLine (string.Join(" ", way));
    }
}

int[][] GetSumWays(int[] array, int k) {
    int[][][] ways = new int[k + 1][][];
    ways[0] = new[] { new int[0] };

    for (int i = 1; i <= k; i++) {
        ways[i] = (
            from val in array
            where i - val >= 0
            from subway in ways[i - val]
            where subway.Length == 0 || subway[0] >= val
            select Enumerable.Repeat(val, 1)
                .Concat(subway)
                .ToArray()
        ).ToArray();
    }

    return ways[k];
}

Output:

1 1 1 1 1 1
1 1 1 1 2
1 1 2 2
2 2 2

It uses a dynamic programming approach and should be faster than a naive recursive approach. I think. I know it's fast enough to count the number of ways to break a dollar in a few milliseconds. (242)