Return to Revisions

I'd approach this in a different way. Looking at the problem I'd sum the different bag capacities until they are \$<= n\$. The moment the sum becomes \$> n\$ I have to stop incresing this sum as it would be useless.

Doing this kind of reasoning I'd go with a tree structure. The max level of the tree should be the number \$k\$ of bags/buckets. The spanning factor for each node in the i-th level is bags[i].capacity + 1 (from 0 to max capacity of the bag).

So, the operations of the algorithm should be the following:

1. Start with an empty tree with a single root
2. Expand the root (insert the nodes for the first level) with the possible elements of the first bag
3. If sum from root to current is > n then there is no need to proceed further on this path. If sum from root to current is == n increase counter and stop expanding this path. If sum from root to current is < n repeat point 2 with the current node instead of the root and by expanding the node with the possible elements of bag[currentLevel + 1].

Regarding the complexity of the algorithm we have that time complexity is \$O(AvgBagCapacity^{NumOfBags})\$ (that is reduced a little by breaking the computation early). Regarding the space complexity depends on the approach used to expand the tree. Personally, I'd suggest to use a depth-first approach as it reduces the space complexity to \$O(AvgBagCapacity * NumOfBags)\$ (if you don't keep the already expanded nodes in memory). If you want to furtherly reduce the space complexity you could use lazy initializations of the nodes so you use only one node at a time. By doing so, the space complexity is \$O(NumOfBags)\$.

For the sake of clarity I wrote some code which does what I described. Obviously it has a lot of room for improvement (starting with the naming :P ). I also included some tests (the first two are the same as two of your examples) so you can do comparisons and play with it.

public class Node
{
    public int[] Buckets { get; set; }
    public int Element { get; set; }
    public int ParentSum { get; set; }
    public int NodeSum { get { return Element + ParentSum; } }
    public int Level { get; set; }

    public IEnumerable<Node> GenerateChildrenForNextLevel()
    {
        if(Level < Buckets.Length - 1)
        {
            var thisNode = this;
        
            for(int i = 0; i <= Buckets[Level + 1]; i++)
            {
                yield return new Node()
                {
                    Element = i,
                    ParentSum = thisNode.NodeSum,
                    Level = thisNode.Level + 1, 
                    Buckets = thisNode.Buckets
                };
            }
        }
        else
        {
            yield return null;
        }
    }

    public int GetNumberOfPermutationsForSum(int sum)
    {
        int numberOfPermutations = 0;
    
        if(NodeSum == sum)
        {
            numberOfPermutations = 1;
        }
        else if(NodeSum < sum)
        {
            var children = GenerateChildrenForNextLevel();
        
            if(children != null)
            {   
                foreach(var child in children)
                {
                    if(child != null)
                    {
                        numberOfPermutations += child.GetNumberOfPermutationsForSum(sum);
                    }
                }
            }
        }
    
        return numberOfPermutations;
    }
}

public class Tree
{
    public int[] Buckets { get; set; }
    public Node Root { get; set; }
    public int TotalSum { get; private set; }

    public Tree(int totalSum, int[] buckets)
    {
        Root = new Node()
        {
            Element = 0,
            ParentSum = 0,
            Level = -1,
            Buckets = buckets
        };
        TotalSum = totalSum;
        Buckets = buckets;
    }

    public int CalculateNumberOfPermutations()
    {
        return Root.GetNumberOfPermutationsForSum(TotalSum);
    }
}

class Program
{
    static void Main()
    {
        int[] buckets1 = new int[] { 4, 4, 2 };
        int[] buckets2 = new int[] { 10, 8, 5};
        int[] buckets3 = new int[] { 20, 19, 18, 17, 16, 
                                 15, 14 };
        Tree tree1 = new Tree(5, buckets1);
        Tree tree2 = new Tree(10, buckets2);
        Tree tree3 = new Tree(30, buckets3);
        int numberOfPermutations1, numberOfPermutations2, numberOfPermutations3;
        Stopwatch sw = new Stopwatch();
    
        sw.Start();
        numberOfPermutations1 = tree1.CalculateNumberOfPermutations();
        sw.Stop();
    
        Console.WriteLine("The number of permutations for the first example is {0} and was calculated in {1}",
                      numberOfPermutations1,
                      sw.Elapsed);
    
        sw.Start();
        numberOfPermutations2 = tree2.CalculateNumberOfPermutations();
        sw.Stop();
      
        Console.WriteLine("The number of permutations for the second example is {0} and was calculated in {1}",
                      numberOfPermutations2,
                      sw.Elapsed);
                      
        sw.Start();
        numberOfPermutations3 = tree3.CalculateNumberOfPermutations();
        sw.Stop();
      
        Console.WriteLine("The number of permutations for the third example is {0} and was calculated in {1}",
                      numberOfPermutations3,
                      sw.Elapsed);
    }
}

Let me know if anything's unclear.