Subset Sum

Given an array of non-negative integers and a value determine if there is a subset of the given array with sum equal to given value.

Dynamic Programming Solution:

Maintain a Boolean 2D matrix say table[][] where the value of table[i][j] will be true if there is a subset of array[0..j-1] with sum equal to i, otherwise false. Obviously table[sum][n] will be our answer.

Implementation in C#:

        public bool IsSubsetSum(int[] arr, int sum)

        {

            if (sum == 0)

            {

                return true;

            }

            if (arr?.Length == 0)

            {

                return false;

            }

            bool[,] table = new bool[sum + 1, arr.Length + 1];

            for (int i = 0; i <= arr.Length; ++i)

            {

                table[0, i] = true;

            }

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

            {

                table[i, 0] = false;

            }

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

            {

                for (int j = 1; j <= arr.Length; ++j)

                {

                    table[i, j] = table[i, j - 1];

                    if (i >= arr[j - 1])

                    {

                        table[i, j] = table[i, j] || table[i - arr[j - 1], j - 1];

                    }

                }

            }

            return table[sum, arr.Length];

        }

Complexity: O(n²)

Limitation: You can see that this solution is not feasible if the sum is too big (Too much memory consumption).

Another approach:

Try all the subsets of the given array and check whether sum of the elements in the subset is equal to given sum or not.

Implementation in C++:

bool isSubsetSum(int *arr, int len, int sum)
{
if(sum == 0)
return true;
if(arr == NULL || len == 0)
return false;
if(arr[len-1] > sum)
return isSubsetSum(arr, len - 1, sum);

return isSubsetSum(arr, len - 1, sum) || isSubsetSum(arr, len - 1, sum - arr[len -1]);
}

Complexity: O(2ⁿ)