Combination Sum II

Problem: Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(2, 1, 1)
(2, 2)

Note that different sequences are counted as different combinations.

Therefore the output is 5.

Approach: We will use DP here. We can maintain a 1D Table of size target + 1 where Target[i] will tell the number of combinations that add up to i. Obviously Table[target] will be our answer. Let's see how we can fill this table:

• Table[0] = 1 // For sum = 0 there is only one way which is to leave all the elements
• FOR i = 1 to target
• FOR j = 0 to n
• IF i >= nums[j]
• Table[i] = Table[i] + Table[i - nums[j]]

That's all!

Implementation in C#:

        public int CombinationSum4(int[] nums, int target)

        {

            if (nums?.Length == 0)

            {

                return 0;

            }

            int[] table = new int[target + 1];

            table[0] = 1;

            for (int i = 1; i <= target; ++i)

            {

                for (int j = 0; j < nums.Length; ++j)

                {

                    if (i >= nums[j])

                    {

                        table[i] += table[i - nums[j]];

                    }

                }

            }

            return table[target];

        }

Complexity: O(m*n) where m is target and n is length of input array