Subset Sum Problem

, , , , ,

Question

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

Integers can appear more than once in the list. You may assume all numbers in the list are positive.

Example

1
2
3
Input: S = [12, 1, 61, 5, 9, 2], k = 24, 
Output: true
 since [12, 9, 2, 1] sums up to 24.

Solution

This is the classical 0-1 Knapsack problem and we can apply into 2D (dp[n+1][k+1]) and then iterate each possibilities. Actually, if we want to show what kind of subset looks like, we can use backtracking.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// time:O(n * k) space:O(n * k)
public boolean subsetSumToTarget(int[] nums, int k) {
        if (nums == null || nums.length == 0) return false;
        int n = nums.length;
        boolean[][] dp = new boolean[n + 1][k + 1];
        
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {
            dp[i][0] = true;
        }
        for (int j = 1; j <= k; j++) {
            dp[0][j] = false;
        }
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= nums[i - 1]) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
                }
            }
        }
        return dp[n][k];
    }

// but we can reduce the space to 1D
// time:O(n * k) space:O(k)
public boolean subsetSumToTarget(int[] nums, int k) {
        if (nums == null || nums.length == 0) return false;
        int n = nums.length;
        boolean[] dp = new boolean[k + 1];
        dp[0] = true;
        for (int num : nums) {
            for (int j = k; j >= num; j--) {
               dp[j] = dp[j] || dp[j - num];
            }
        }
        return dp[k];
    }

Reference