Subset Sum

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

Examples: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output:  True  //There is a subset (4, 5) with sum 9.

Java (bottom-up)
Time complexity: O(N*M), N – size of array, M – target sum
Space complexity: O(N*M), N – size of array, M – target sum

public class SubSetSum {

    public boolean sumsTo(int[] nums, int sum){
        if (nums == null || nums.length == 0 || sum < 0){
            return false;
        }

        boolean[][] dp = new boolean[nums.length][sum+1];

        for (int i = 0; i < nums.length; ++i){
            dp[i][0] = true;
        }

        for (int i = 0; i < dp.length; ++i){
            for (int j = 1; j < dp[0].length; ++j){
                if (i == 0 && nums[i] == j){
                    dp[i][j] = true;
                } else if (i == 0){
                    continue;
                }else {
                    dp[i][j] = dp[i-1][j] || (nums[i] <= j ? dp[i-1][j - nums[i]] : false);
                }

            }
        }

        return dp[nums.length - 1][sum];
    }

}

Python (top-down)
Time complexity: O(2^N), N – size of array
Space complexity: O(N), N – size of array

def sumsTo(nums, sum):
    if not len(nums) or sum < 0:
        return False

    dp = [None] * len(nums)
    return checkSumsTo(nums, 0, sum, dp)

def checkSumsTo(nums, idx, sum, dp):
    if sum == 0:
        return True
    elif sum < 0 or idx >= len(nums):
        return False
    elif idx < len(nums) and dp[idx]:
        return dp[idx]

    notInclude = checkSumsTo(nums, idx+1, sum, dp)
    include = checkSumsTo(nums, idx+1, sum - nums[idx], dp)
    dp[idx] = notInclude or include

    return dp[idx]
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s