0

Problem: Given a number 'a' and number 'b'. Find all the combinations whose size is 'a' and sum of the numbers in the combination should be equal to 'b'.

Example: a = 3, b = 5. For simplicity consider only whole numbers. Combinations - { (0, 0, 5}, (1, 1, 3), (1, 2, 2), (0, 1, 4), (0, 2, 3)}. {1, 3, 1} is not a valid combination because (1, 1, 3) is already in the solution.

Here is my solution.

    public void CombinationsMain()
    {
        Console.Write("Enter the target sum: ");
        string tsum = Console.ReadLine();
        Console.Write("Enter the number of combinations: ");

        string combination = Console.ReadLine();
        int targetsum;
        Int32.TryParse(tsum, out targetsum);
        int m;
        Int32.TryParse(combination, out m);
        int[] arr = new int[m];
        CombinationsUtil(targetsum, 0, arr);
        Console.ReadLine();
    }

    public void CombinationsUtil(int targetsum, int index, int[] arr)
    {
        //check if the length of the current index is same as arr length and sum 
        //before printing the combination
        //SumofArrayElements ignores the combination like {0 0 5 0} { 0 5 0 0} and will print only { 0 0 0 5}
        if (index == arr.Length && SumOfArrayElements(arr, targetsum))
        {
            for (int i = 0; i < arr.Length; i++)
                Console.Write(arr[i]);
            Console.WriteLine();
        }

        for (int i = 0; i <= targetsum && index < arr.Length; i++)
        {
            arr[index] = i;
            CombinationsUtil(targetsum, index + 1, arr);
        }
    }

    //returns true or false comparing sum of elements of array and given target sum
    public bool SumOfArrayElements(int[] arr, int targetsum)
    {

        int sum = 0;
        for (int i = 0; i < arr.Length; i++)
        {
            if (i < arr.Length-1 && arr[i] > arr[i + 1])
                return false;
            sum += arr[i];
        }
        return sum == targetsum;
    }

Time complexity is O(n^m) (n here is targetsum). Can it be optimized any further or is this the best I can do? Thanks for your inputs.

Kar
  • 105
  • 11
  • Your internal documentation leaves a couple of open issues; please clarify. What is **m**? You use it to parametrize the summation array **arr**, but I don't see a rationale. In contrast, your example gives a length of b=3. I see both n and sumvalue as 5; what are these two parameters? You list the complexity as O(n^r); what is r? – Prune Feb 10 '16 at 23:23
  • 1
    Possible duplicate of [Is there an efficient algorithm for integer partitioning with restricted number of parts?](http://stackoverflow.com/questions/32907406/is-there-an-efficient-algorithm-for-integer-partitioning-with-restricted-number) – m69's been on strike for years Feb 11 '16 at 03:42
  • @Prune: m is the number of elements in the combination. For m=4 and targetsum=5 a combinations could be {0,0, 0, 5}, {1, 1, 1, 2}. It was a typo. It is O(n^m)( n here is targetsum) – Kar Feb 11 '16 at 16:24
  • @m69: the link is helpful. Thanks – Kar Feb 11 '16 at 16:44

0 Answers0