Subset Sum Problem 1 - Is there a subset?

Problem

Given a list of integers S and a target number k, write a function that returns a true if there is subset of S that adds up to k. If such a subset cannot be made, then return false.

Examples

Example 1:

nums = [2, 3, 5], k = 7
Output: true
Explanation: Subset is [2, 5]

Example 2:

nums = [3, 34, 4, 12, 5, 2], k = 9
Output: true
Explanation: Subset is [4, 5]

Example 3:

nums = [2, 3, 5], k = 1
Output: false
Explanation: Subset is [2, 5]

Similar Problems

• Generate All Strings of n bits

Solution

Method 1 - Recursive Solution

For every element in the array has two options, either we will include that element in subset or we don’t include it.

We can start with 0th index idx, and take those cases, and whenever:

• We include the number num, and then reduce targetSum by num and go to next number at idx+1
  • At any point in the dfs, if we find targetSum = 0, we have found the answer to be true.
• We exclude the number num, but go to next number idx + 1

Code

Java

class Solution {

	public static boolean hasSubsetSum(int[] nums, int k) {
		return dfs(nums, k, 0);
	}

	private boolean dfs(int[] nums, int targetSum, int idx) {
		if (targetSum == 0) {
			return true;
		}

		if (idx == nums.length || targetSum < 0) {
			return false;
		}

		boolean include = dfs(nums, targetSum - nums[idx], idx + 1);
		boolean exclude = dfs(nums, targetSum, idx + 1);

		return include || exclude;
	}
}

Complexity

• ⏰ Time complexity: O(2^n)
• 🧺 Space complexity: O(n) assuming recursion stack

Method 2 - Dynamic Programming Top Down

We can use dynamic programming to memoize the solutions to subproblems. Following is the memoized dynamic programming solution.

Code

Java

Using Boolean array

public class SubsetSumTopDown {
    public boolean hasSubsetSum(int[] nums, int k) {
        return dfs(nums, k, 0, new Boolean[k + 1][targetSum + 1]);
    }

	private boolean dfs(int[] nums, int targetSum, int idx, Boolean[][] memo) {
		if (targetSum == 0) {
			return true;
		}

		if (idx == nums.length || targetSum < 0) {
			return false;
		}

		if (memo[idx][targetSum] != null) {
			return memo[idx][targetSum];
		}

		boolean include = dfs(nums, targetSum - nums[idx], idx + 1, memo);
		boolean exclude = dfs(nums, targetSum, idx + 1, memo);

		return memo[idx][targetSum] = (include || exclude);
	}
}

Using HashMap

public class SubsetSumTopDown {
    public boolean hasSubsetSum(int[] nums, int k) {
        return dfs(nums, k, 0, new HashMap<String, Boolean>());
    }

	private boolean dfs(int[] nums, int targetSum, int idx, Map<String, Boolean> memo) {
		if (targetSum == 0) {
			return true;
		}

		if (idx == nums.length || targetSum < 0) {
			return false;
		}
		
		String key = idx + "-" + targetSum;
		if (memo.containsKey(key)) {
			return memo.get(key);
		}

		boolean include = dfs(nums, targetSum - nums[idx], idx + 1, memo);
		boolean exclude = dfs(nums, targetSum, idx + 1, memo);
	
		memo.put(key, include || exclude);
		
		return memo.get(key);
	}
}

Complexity

• ⏰ Time complexity: O(n*k), where n is the number of items in the nums array and k is the target sum. Each state defined by a particular idx and targetSum is computed at most once. Since idx can range from 0 to n and targetSum can range from 0 to k, there are n * k possible states.
• 🧺 Space complexity: O(n*k)

Method 3 - Dynamic Programming Bottom up

Algorithm

1. Initialise a dp table of size len(S) * k
2. Set the entire first column to True (this just means that a 0 sum is always possible)
3. For every row (for every item in the set S):
   • For every column (sum):
     • For the very first row only: If the sum < item, set it to False
     • Check the value of the cell directly above it, and directly above it with sum rows back
       • If either is true, set it to True— else False
4. The item in the bottom-right-most position will say if the subset sum is possible or not.

Code

Java

class Solution {

	public boolean hasSubsetSum(int[] nums, int targetSum) {
		boolean[][] dp = new boolean[nums.length + 1][targetSum + 1];

		// if targetSum is not zero and subset is 0, we can't make it
		for (int i = 1; i <= targetSum; i++) {
			dp[0][i] = false;
		}

		// if targetSum is 0 the we can make the empty subset to make sum 0
		for (int i = 0; i <= nums.length; i++) {
			dp[i][0] = true;
		}

		//
		for (int i = 1; i <= nums.length; i++) {
			for (int j = 1; j <= targetSum; j++) {
				// first copy the data from the top
				dp[i][j] = dp[i - 1][j];

				// If dp[i][j]==false check if can be made
				if (dp[i][j] == false && j >= nums[i - 1]) {
					dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
				}
			}
		}

		return dp[nums.length][targetSum];
	}

}

Complexity

• ⏰ Time complexity: O(n*k), where n is the number of items in the nums array and k is the target sum.
• 🧺 Space complexity: O(n*k)

Dry Run

nums = [2, 3, 5], targetSum = 7

Lets start filling the DP table.

if targetSum is not zero and subset is 0, we can’t make it

If targetSum is 0 the we can make the empty subset to make sum 0:

Now lets fill for the element 2 in set. We can make a subset with sum 2 using the first number 2.

Now lets fill for the element 3 in set. We can make a subset with sum 3 using just the number 3. We can make 5 using both 2 and 3.

Row nums[2]=5: - We retain the ability to make 2 and 3 because if we can make a sum without using the new number (nums[2] in this row), we carry over that ability. - We can now make 5 because we can use the number 5 by itself. - We can make 6 using 2 and 5 or just using 2 and 3 from previous rows. - We can make 7 by using 2 and 5.

Since dp[nums.length][targetSum] == dp[3][7] is true, the subset sum of 7 is achievable with the provided array nums.