CODEWITHSUNDEEP
c#combinationssubset-sum
Ali Tor
Ali Tor

Reputation: 2945

How to find all subset which is the summation of its elements equals to a constant number?

I need to find all number subset to get a number N by summing its elements. I don't know how to get through this type of combination problem. In this combination, order matters for different numbers.

example for the number N=4

1 + 1 + 1 + 1
2 + 1 + 1
1 + 2 + 1
1 + 1 + 2
2 + 2
3 + 1
1 + 3

Zeros are not important for me. So how can I get such number sets as an array for an exact number?

Upvotes: 0

Views: 93

Answers (2)

user6732794
user6732794

Reputation:

What you're looking for are called integer compositions, or ordered partitions.

Compositions can be generated recursively (in lexicographic order, if I'm not mistaken) as follows:

public static IEnumerable<List<int>> Compositions(int n)
{
    if (n < 0)
        throw new ArgumentOutOfRangeException(nameof(n));

    return GenerateCompositions(n, new List<int>());
}

private static IEnumerable<List<int>> GenerateCompositions(int n, List<int> comp)
{
    if (n == 0)
    {
        yield return new List<int>(comp); // important: must make a copy here
    }
    else
    {
        for (int k = 1; k <= n; k++)
        {
            comp.Add(k);

            foreach (var c in GenerateCompositions(n - k, comp)) 
                yield return c;

            comp.RemoveAt(comp.Count - 1);
        }
    }
}

Not tested! This was transcribed from a Python implementation. If anyone would like to make corrections or update the code with more idiomatic C#, feel free.

Also, as @aah noted, the number of compositions of n is 2^(n-1), so this becomes unwieldy even for modest n.

Upvotes: 1

aah
aah

Reputation: 91

If order doesn't matter, there are simply 2^(N-1) possibilities. (Your example doesn't have 2 + 2 or 4)

You can then represent any sequence by its binary representation. To generate, imagine N 1's in a row, so there are N-1 "spaces" between them. Choosing any subset of spaces, you merge any 1's that are adjacent via a chosen space. You can verify this is 1-1 to all possible sets by expanding any such sequence and inserting these spaces.

Upvotes: 0

Related Questions