Subset sum algorithm with repetition of numbers in the set

Question

I have a set S containing natural numbers and a target t which is an number. I want to know
how can we find the number of possible combinations of these numbers which sums up to target t.
A number can be taken any number of times and any number of numbers can be taken for getting the
sum equal to the target t.

Example
target  6
Set s  {3,8,1,2}
Solution   3+3, 3+2+1, 1+1+1+3, 2+2+2, 2+1+1+2, 2+1+1+1+1, 1+1+1+1+1+1
Total No of solutions possible  7

What can be the efficient algorithm for this?

Answer 1

If the target is reasonably small, you can use dynamic programming to obtain an O(|S| * t) solution. Here is a sample code in Python:

def combinations(S, t):
    dp = [1] + [0] * t
    for i in S:
        for j in range(0, t - i + 1):
            dp[j + i] += dp[j]
    return dp[t]

Answer 2

If you not only need the number of results but also the result sets themselves, you can use this recursive approach (C# code):

public class SubsetSumSolverService
{
    public IList<List<TSource>> Solve<TSource>(IEnumerable<TSource> source, Func<TSource, decimal> getDecimal, decimal goal)
    {
        if (source == null) { throw new ArgumentNullException(nameof(source)); }
        if (getDecimal == null) { throw new ArgumentNullException(nameof(getDecimal)); }

        if (!source.Any()) { throw new ArgumentException("List must not be empty", nameof(source)); }
        var values = source.OrderBy(s => getDecimal(s)).ToArray();
        if (getDecimal(values.First()) <= 0) { throw new ArgumentException("Only positive values are supported", nameof(source)); }
        var results = new List<List<TSource>>();
        SolveRecursive(values: values, position: 0, state: new List<TSource>(), stateValue: 0, goal: goal, getDecimal: getDecimal, results: results);
        return results;
    }

    private void SolveRecursive<TSource>(TSource[] values, int position, List<TSource> state, decimal stateValue, decimal goal, Func<TSource, decimal> getDecimal, List<List<TSource>> results)
    {
        var currentPosition = -1;
        foreach (var value in values.Skip(position))
        {
            currentPosition++;
            var currentValue = getDecimal(value);
            var nextValue = currentValue + stateValue;
            if (nextValue > goal)
            {
                break;
            }

            var newList = new List<TSource>(state)
            {
                value,
            };
            if (nextValue == goal)
            {
                results.Add(newList);
            }
            else
            {
                SolveRecursive(values, currentPosition, newList, nextValue, goal, getDecimal, results);
            }
        }
    }
}

Usage and test code:

[TestClass]
public class SubsetSumSolverServiceTests
{
    private class X
    {
        public string S { get; set; }

        public X(string s, decimal value)
        {
            S = s;
            Value = value;
        }

        public decimal Value { get; set; }

        public override string ToString()
        {
            return $"{Value} ({S})";
        }
    }

    [TestMethod]
    public void SubsetSumSolverTest()
    {
        var service = new SubsetSumSolverService();

        List<X> list;
        IList<List<X>> result;
        var one = new X("one", 1);
        var oneOther = new X("one_", 1);
        var two = new X("two", 2);
        var three = new X("three", 3);
        var pointFive = new X("0.5", 0.5m);
        var five = new X("five", 5);
        var six = new X("six", 6);

        list = new List<X> { one, two };
        result = service.Solve(list, e => e.Value, 2);
        AssertListList(new List<List<X>> {
            new List<X> { one, one },
            new List<X> { two },
        }, result);

        list = new List<X> { three, one, two };
        result = service.Solve(list, e => e.Value, 2);
        AssertListList(new List<List<X>> {
            new List<X> { one, one },
            new List<X> { two },
        }, result);

        list = new List<X> { three, one, two };
        result = service.Solve(list, e => e.Value, 3);
        AssertListList(new List<List<X>> {
            new List<X> { one, one, one },
            new List<X> { one, two },
            new List<X> { three },
        }, result);

        list = new List<X> { one, three, oneOther, two, };
        result = service.Solve(list, e => e.Value, 3);
        AssertListList(new List<List<X>> {
            new List<X> { one, one, one },
            new List<X> { one, one, oneOther },
            new List<X> { one, oneOther, oneOther, },
            new List<X> { one, two },
            new List<X> { oneOther, oneOther, one,},
            new List<X> { oneOther, oneOther, oneOther,},
            new List<X> { oneOther, two },
            new List<X> { three },
        }, result);

        list = new List<X> { one, pointFive, two, };
        result = service.Solve(list, e => e.Value, 2.5m);
        AssertListList(new List<List<X>> {
            new List<X> { pointFive, pointFive, pointFive, pointFive, pointFive },
            new List<X> { pointFive, pointFive, pointFive, one, },
            new List<X> { pointFive, one, one, },
            new List<X> { pointFive, two, },
            new List<X> { one, one, pointFive, },
        }, result);

        list = new List<X> { one, five, six };
        result = service.Solve(list, e => e.Value, 7);
        AssertListList(new List<List<X>> {
            new List<X> { one, one, one, one, one, one, one },
            new List<X> { one, one, five, },
            new List<X> { one, six, },
        }, result);

        list = new List<X> { five, six };
        result = service.Solve(list, e => e.Value, 30);
        AssertListList(new List<List<X>> {
            new List<X> { five, five, five, five, five, five, },
            new List<X> { six, six, six, six, six },
        }, result);
    }

    private static void AssertListList(List<List<X>> expected, IList<List<X>> actual)
    {
        Assert.AreEqual(expected.Count, actual.Count, "Wrong number of elements in lists");
        var expectedEnumerator = expected.GetEnumerator();
        var actualEnumerator = actual.GetEnumerator();
        while (expectedEnumerator.MoveNext())
        {
            var expectedCurrent = expectedEnumerator.Current;
            actualEnumerator.MoveNext();
            var actualCurrent = actualEnumerator.Current;
            CollectionAssert.AreEquivalent(expectedCurrent, actualCurrent);
        }
    }
}