Knapsack, Weight-Only

Prereqs: Backtracking, Memoization

Given a list of weights of n items, find all sums that can be formed using their weights.

Input

weights: A list of n positive integers, representing weights of the items

Output

A list, in any order, of the unique sums that can be obtained by using combinations of the provided weights

Examples

Example 1:

Input:

weights = [1, 3, 3, 5]

Output: [0, 1, 3, 4, 5, 6, 7, 8, 9, 11, 12]

Explanation:

We can form all sums from 0 to 12 except 2 and 10. Here is a short explanation for the sums:

0: use none of the weights
1: use item with weight 1
3: use item with weight 3
4: use weights 1 + 3 = 4
5: use item with weight 5
6: use weights 3 + 3 = 6
7: use weights 1 + 3 + 3 = 7
8: use weights 3 + 5 = 8
9: use weights 1 + 3 + 5 = 9
11: use weights 3 + 3 + 5 = 11
12: use all weights

Constraints

1 <= len(weights) <= 100
1 <= weights[i] <= 100

Try it yourself

Solution

Brute Force

A brute force method enumerates all possibilities. We start with a total sum of 0 and process every item by either choosing to include it into our sum or not into our sum. Once no more items are left to process, we can include the final sum in a list of sums. Additionally, we will store these sums in a set since there can be repeating sums.

By going through every possibility, we're generating all possible subsets, so we guarantee that we are also generating all possible sums.

Since there are n items, two possibilities each, and it takes O(1) to compute each possibility, the final runtime is O(2^n).

The following is the state-space tree for this idea using input [1, 3, 3, 5]. Each level i of the tree represents a binary decision to include or not include the ith number. For example, we have two branches in level i = 1, the left branch means not picking the ith item 3, and the right branch means picking it.

Here is the code for the idea above:

1from typing import List, Set
2
3def generate_sums(weights: List[int], sums: Set[int], total: int, n: int) -> None:
4    if n == 0:
5        sums.add(total)
6        return
7    generate_sums(weights, sums, total, n - 1)
8    generate_sums(weights, sums, total + weights[n - 1], n - 1)
9
10def knapsack_weight_only(weights: List[int]) -> List[int]:
11    sums: Set[int] = set()
12    n = len(weights)
13    generate_sums(weights, sums, 0, n)
14    return list(sums)
15
16if __name__ == "__main__":
17    weights = [int(x) for x in input().split()]
18    res = knapsack_weight_only(weights)
19    print(" ".join(map(str, sorted(res))))
20

1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.HashSet;
4import java.util.List;
5import java.util.Scanner;
6import java.util.Set;
7import java.util.stream.Collectors;
8
9class Solution {
10    public static void generateSums(List<Integer> weights, Set<Integer> sums, int sum, int n) {
11        if (n == 0) {
12            sums.add(sum);
13            return;
14        }
15        generateSums(weights, sums, sum, n - 1);
16        generateSums(weights, sums, sum + weights.get(n - 1), n - 1);
17    }
18
19    public static List<Integer> knapsackWeightOnly(List<Integer> weights) {
20        Set<Integer> sums = new HashSet<>();
21        int n = weights.size();
22        generateSums(weights, sums, 0, n);
23        return new ArrayList<>(sums);
24    }
25
26    public static List<String> splitWords(String s) {
27        return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
28    }
29
30    public static void main(String[] args) {
31        Scanner scanner = new Scanner(System.in);
32        List<Integer> weights = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
33        scanner.close();
34        List<Integer> res = knapsackWeightOnly(weights);
35        System.out.println(res.stream().sorted().map(String::valueOf).collect(Collectors.joining(" ")));
36    }
37}
38

1"use strict";
2
3function generateSums(weights, sums, sum, n) {
4    if (n === 0) {
5        sums.add(sum);
6        return;
7    }
8    generateSums(weights, sums, sum, n - 1);
9    generateSums(weights, sums, sum + weights[n - 1], n - 1);
10}
11
12function knapsackWeightOnly(weights) {
13    const sums = new Set();
14    const n = weights.length;
15    generateSums(weights, sums, 0, n);
16    return Array.from(sums);
17}
18
19function splitWords(s) {
20    return s === "" ? [] : s.split(" ");
21}
22
23function* main() {
24    const weights = splitWords(yield).map((v) => parseInt(v));
25    const res = knapsackWeightOnly(weights);
26    console.log(res.sort((a, b) => a - b).join(" "));
27}
28
29class EOFError extends Error {}
30{
31    const gen = main();
32    const next = (line) => gen.next(line).done && process.exit();
33    let buf = "";
34    next();
35    process.stdin.setEncoding("utf8");
36    process.stdin.on("data", (data) => {
37        const lines = (buf + data).split("\n");
38        buf = lines.pop();
39        lines.forEach(next);
40    });
41    process.stdin.on("end", () => {
42        buf && next(buf);
43        gen.throw(new EOFError());
44    });
45}
46

1#include <algorithm>
2#include <iostream>
3#include <iterator>
4#include <sstream>
5#include <string>
6#include <unordered_set>
7#include <vector>
8
9void generate_sums(std::vector<int>& weights, std::unordered_set<int>& sums, int sum, int n) {
10    if (n == 0) {
11        sums.emplace(sum);
12        return;
13    }
14    generate_sums(weights, sums, sum, n - 1);
15    generate_sums(weights, sums, sum + weights[n - 1], n - 1);
16}
17
18std::vector<int> knapsack_weight_only(std::vector<int>& weights) {
19    std::unordered_set<int> sums;
20    int n = weights.size();
21    generate_sums(weights, sums, 0, n);
22    return {sums.begin(), sums.end()};
23}
24
25template<typename T>
26std::vector<T> get_words() {
27    std::string line;
28    std::getline(std::cin, line);
29    std::istringstream ss{line};
30    ss >> std::boolalpha;
31    std::vector<T> v;
32    std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
33    return v;
34}
35
36template<typename T>
37void put_words(const std::vector<T>& v) {
38    if (!v.empty()) {
39        std::copy(v.begin(), std::prev(v.end()), std::ostream_iterator<T>{std::cout, " "});
40        std::cout << v.back();
41    }
42    std::cout << '\n';
43}
44
45int main() {
46    std::vector<int> weights = get_words<int>();
47    std::vector<int> res = knapsack_weight_only(weights);
48    std::sort(res.begin(), res.end());
49    put_words(res);
50}
51

Top-down Dynamic Programming

First, the "top-down" solution is, basically, the brute force solution but with memoization. We store results that have already been computed and return them once needed. But in precisely what way should we store/represent the data? Going back to the idea of dynamic programming, we should consider what is important so far and if any of the information has been recomputed.

Memoization, identifying the state

To memoize, we need to find the duplicate subtrees in the state-space tree.

Notice that the duplicate subtrees are of the same level for this problem. This isn't a coincidence.

Unlike Word Break and Decode Ways in the backtracking section, the items in the knapsack problem can only be used once.

Consider Node A and Node B in the tree:

Node B's subtree has leaf values of 3 and 8. And Node A's subtree has leaf values of 3, 8, 6, 11. They are clearly not the same subtree. This is because the meaning of a node's value is the weight sum by considering items from 0 to i.

Therefore, the state we need to memoize consists of the level/depth of the node and the node value itself. We will use (i, sum) to denote this.

Thus, we will store a 2D boolean array memo where memo[i][sum] = true if the (i, sum) pair has already been computed and false otherwise. The size of the array is n * total_sum where n is the number of items and total_sum is the weight sum of all items. We need a slot for each possible weight we can make up, and all the possible weights are in the range of 0 to total_sum.

Here is the implementation of the idea:

1from typing import List, Set
2
3def generate_sums(
4    weights: List[int],
5    sums: Set[int],
6    total: int,
7    n: int,
8    memo: List[List[bool]],
9) -> None:
10    if memo[n][total]:
11        return
12    if n == 0:
13        sums.add(total)
14        return
15    generate_sums(weights, sums, total, n - 1, memo)
16    generate_sums(weights, sums, total + weights[n - 1], n - 1, memo)
17    memo[n][total] = True
18
19def knapsack_weight_only(weights: List[int]) -> List[int]:
20    sums: Set[int] = set()
21    n = len(weights)
22    # find total sum of weights
23    total_sum = sum(weights)
24    memo = [[False] * (total_sum + 1) for _ in range(n + 1)]
25    generate_sums(weights, sums, 0, n, memo)
26    return list(sums)
27
28if __name__ == "__main__":
29    weights = [int(x) for x in input().split()]
30    res = knapsack_weight_only(weights)
31    print(" ".join(map(str, sorted(res))))
32

1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.HashSet;
4import java.util.List;
5import java.util.Scanner;
6import java.util.Set;
7import java.util.stream.Collectors;
8
9class Solution {
10    public static void generateSums(List<Integer> weights, Set<Integer> sums, int sum, int n, boolean[][] memo) {
11        if (memo[n][sum]) {
12            return;
13        }
14        if (n == 0) {
15            sums.add(sum);
16            return;
17        }
18        generateSums(weights, sums, sum, n - 1, memo);
19        generateSums(weights, sums, sum + weights.get(n - 1), n - 1, memo);
20        memo[n][sum] = true;
21    }
22
23    public static List<Integer> knapsackWeightOnly(List<Integer> weights) {
24        Set<Integer> sums = new HashSet<>();
25        int n = weights.size();
26        // find total sum of all items
27        int totalSum = 0;
28        for (int weight : weights) {
29            totalSum += weight;
30        }
31        // initialize memo table to store if result has been calculated
32        boolean[][] memo = new boolean[n + 1][totalSum + 1];
33        for (int i = 0; i < n + 1; i++) {
34            Arrays.fill(memo[i], false);
35        }
36        generateSums(weights, sums, 0, n, memo);
37        List<Integer> ans = new ArrayList<>();
38        ans.addAll(sums);
39        return ans;
40    }
41
42    public static List<String> splitWords(String s) {
43        return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
44    }
45
46    public static void main(String[] args) {
47        Scanner scanner = new Scanner(System.in);
48        List<Integer> weights = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
49        scanner.close();
50        List<Integer> res = knapsackWeightOnly(weights);
51        System.out.println(res.stream().sorted().map(String::valueOf).collect(Collectors.joining(" ")));
52    }
53}
54

1"use strict";
2
3function generateSums(weights, sums, sum, n, memo) {
4    if (memo[n][sum]) {
5        return;
6    }
7    if (n === 0) {
8        sums.add(sum);
9        return;
10    }
11    generateSums(weights, sums, sum, n - 1, memo);
12    generateSums(weights, sums, sum + weights[n - 1], n - 1, memo);
13    memo[n][sum] = true;
14}
15
16function knapsackWeightOnly(weights) {
17    const sums = new Set();
18    const n = weights.length;
19    // find total sum of all items
20    let totalSum = 0;
21    for (const weight of weights) {
22        totalSum += weight;
23    }
24    // initialize memo table to store if result has been calculated
25    const memo = new Array(n + 1);
26    for (let i = 0; i < n + 1; i++) {
27        memo[i] = new Array(totalSum + 1);
28        for (let j = 0; j < totalSum + 1; j++) {
29            memo[i][j] = false;
30        }
31    }
32    generateSums(weights, sums, 0, n, memo);
33    return Array.from(sums);
34}
35
36function splitWords(s) {
37    return s === "" ? [] : s.split(" ");
38}
39
40function* main() {
41    const weights = splitWords(yield).map((v) => parseInt(v));
42    const res = knapsackWeightOnly(weights);
43    console.log(res.sort((a, b) => a - b).join(" "));
44}
45
46class EOFError extends Error {}
47{
48    const gen = main();
49    const next = (line) => gen.next(line).done && process.exit();
50    let buf = "";
51    next();
52    process.stdin.setEncoding("utf8");
53    process.stdin.on("data", (data) => {
54        const lines = (buf + data).split("\n");
55        buf = lines.pop();
56        lines.forEach(next);
57    });
58    process.stdin.on("end", () => {
59        buf && next(buf);
60        gen.throw(new EOFError());
61    });
62}
63

1#include <algorithm>
2#include <iostream>
3#include <iterator>
4#include <numeric>
5#include <sstream>
6#include <string>
7#include <unordered_set>
8#include <vector>
9
10void generate_sums(std::vector<int>& weights, std::unordered_set<int>& sums, int sum, int n, std::vector<std::vector<bool>>& memo) {
11    if (memo[n][sum]) {
12        return;
13    }
14    if (n == 0) {
15        sums.insert(sum);
16        return;
17    }
18    generate_sums(weights, sums, sum, n - 1, memo);
19    generate_sums(weights, sums, sum + weights[n - 1], n - 1, memo);
20    memo[n][sum] = true;
21}
22
23std::vector<int> knapsack_weight_only(std::vector<int>& weights) {
24    std::unordered_set<int> sums;
25    int n = weights.size();
26    // find total sum of all items
27    int total_sum = std::accumulate(weights.begin(), weights.end(), 0);
28    // initialize memo table to store if result has been calculated
29    std::vector<std::vector<bool>> memo(n + 1, std::vector<bool>(total_sum + 1, false));
30    generate_sums(weights, sums, 0, n, memo);
31    return {sums.begin(), sums.end()};
32}
33
34template<typename T>
35std::vector<T> get_words() {
36    std::string line;
37    std::getline(std::cin, line);
38    std::istringstream ss{line};
39    ss >> std::boolalpha;
40    std::vector<T> v;
41    std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
42    return v;
43}
44
45template<typename T>
46void put_words(const std::vector<T>& v) {
47    if (!v.empty()) {
48        std::copy(v.begin(), std::prev(v.end()), std::ostream_iterator<T>{std::cout, " "});
49        std::cout << v.back();
50    }
51    std::cout << '\n';
52}
53
54int main() {
55    std::vector<int> weights = get_words<int>();
56    std::vector<int> res = knapsack_weight_only(weights);
57    std::sort(res.begin(), res.end());
58    put_words(res);
59}
60

Since there are n * totalSum states, each state depends on O(1) subproblems, and each state takes O(1) to compute, and the final runtime is O(n * totalSum). Having n * totalSum different states also gives us a memory complexity of O(n * totalSum) with this approach.

Bottom-up Dynamic Programming

Now let's talk about the "bottom-up" solution. Recall that the idea of any bottom-up solution is to start from the smallest cases and work your way up to larger problems. The solution starts from the base case: 0 items can make up a knapsack of weight 0. Then, we can build up more plausible weights by combining the existing plausible weights by a new item. We continue this process until we get to our desired solution, that is, when we have used up all the weights. Thus, by looping through each item, we determine which sums we can construct based on if there exists a smaller sum that we can build on top of. For example, suppose we already built all possible sums using [1, 3, 3], and we wanted to know which sums we can build using all of [1, 3, 3, 5] now. The following is an illustration of this idea:

And here's the code for the iterative/bottom-up solution:

1from typing import List
2
3def knapsack_weight_only(weights: List[int]) -> List[int]:
4    n = len(weights)
5    total_sum = sum(weights)
6    dp = [[False for _ in range(total_sum + 1)] for _ in range(n + 1)]
7    dp[0][0] = True
8    for i in range(1, n + 1):
9        for w in range(total_sum + 1):
10            # vertical blue arrow in the above slides
11            dp[i][w] = dp[i][w] or dp[i - 1][w]
12            # diagonal blue arrow in the above slides
13            # make sure the current item's weight is smaller than the target weight w
14            if w - weights[i - 1] >= 0:
15                dp[i][w] = dp[i][w] or dp[i - 1][w - weights[i - 1]]
16    ans = []
17    # check the last row for all possible answers
18    for w in range(total_sum + 1):
19        if dp[n][w]:
20            ans.append(w)
21    return ans
22
23if __name__ == "__main__":
24    weights = [int(x) for x in input().split()]
25    res = knapsack_weight_only(weights)
26    print(" ".join(map(str, sorted(res))))
27

1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4import java.util.Scanner;
5import java.util.stream.Collectors;
6
7class Solution {
8    public static List<Integer> knapsackWeightOnly(List<Integer> weights) {
9        int n = weights.size();
10        int totalSum = 0;
11        for (int weight : weights) {
12            totalSum += weight;
13        }
14        boolean[][] dp = new boolean[n + 1][totalSum + 1];
15        dp[0][0] = true;
16        for (int i = 1; i <= n; i++) {
17            for (int w = 0; w <= totalSum; w++) {
18                // vertical blue arrow in the above slides
19                dp[i][w] = dp[i][w] || dp[i - 1][w];
20                // diagonal blue arrow in the above slides
21                // make sure current item's weight is smaller than the target weight w
22                if (w - weights.get(i - 1) >= 0) {
23                    dp[i][w] = dp[i][w] || dp[i - 1][w - weights.get(i - 1)];
24                }
25            }
26        }
27        List<Integer> ans = new ArrayList<>();
28        // check the last row for all possible answers
29        for (int w = 0; w <= totalSum; w++) {
30            if (dp[n][w]) {
31                ans.add(w);
32            }
33        }
34        return ans;
35    }
36
37    public static List<String> splitWords(String s) {
38        return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
39    }
40
41    public static void main(String[] args) {
42        Scanner scanner = new Scanner(System.in);
43        List<Integer> weights = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
44        scanner.close();
45        List<Integer> res = knapsackWeightOnly(weights);
46        System.out.println(res.stream().sorted().map(String::valueOf).collect(Collectors.joining(" ")));
47    }
48}
49

1"use strict";
2
3function knapsackWeightOnly(weights) {
4    const n = weights.length;
5    let totalSum = 0;
6    for (const weight of weights) {
7        totalSum += weight;
8    }
9    const dp = new Array(n + 1).fill().map(() => new Array(totalSum + 1).fill(false));
10    dp[0][0] = true;
11    for (let i = 1; i <= n; i++) {
12        for (let w = 0; w <= totalSum; w++) {
13            // vertical blue arrow in the above slides
14            dp[i][w] ||= dp[i - 1][w];
15            // diagonal blue arrow in the above slides
16            // make sure current item's weight is smaller than the target weight w
17            if (w - weights[i - 1] >= 0) {
18                dp[i][w] ||= dp[i - 1][w - weights[i - 1]];
19            }
20        }
21    }
22    const ans = [];
23    // check the last row for all possible answers
24    for (let w = 0; w <= totalSum; w++) {
25        if (dp[n][w]) {
26            ans.push(w);
27        }
28    }
29    return ans;
30}
31
32function splitWords(s) {
33    return s === "" ? [] : s.split(" ");
34}
35
36function* main() {
37    const weights = splitWords(yield).map((v) => parseInt(v));
38    const res = knapsackWeightOnly(weights);
39    console.log(res.sort((a, b) => a - b).join(" "));
40}
41
42class EOFError extends Error {}
43{
44    const gen = main();
45    const next = (line) => gen.next(line).done && process.exit();
46    let buf = "";
47    next();
48    process.stdin.setEncoding("utf8");
49    process.stdin.on("data", (data) => {
50        const lines = (buf + data).split("\n");
51        buf = lines.pop();
52        lines.forEach(next);
53    });
54    process.stdin.on("end", () => {
55        buf && next(buf);
56        gen.throw(new EOFError());
57    });
58}
59

1#include <algorithm>
2#include <iostream>
3#include <iterator>
4#include <sstream>
5#include <string>
6#include <vector>
7
8std::vector<int> knapsack_weight_only(std::vector<int> weights) {
9    int n = weights.size();
10    int total_sum = 0;
11    for (int weight : weights) {
12        total_sum += weight;
13    }
14    std::vector<std::vector<bool>> dp(n + 1, std::vector<bool>(total_sum + 1, false));
15    dp[0][0] = true;
16    for (int i = 1; i <= n; i++) {
17        for (int w = 0; w <= total_sum; w++) {
18            // vertical blue arrow in the above slides
19            dp[i][w] = dp[i][w] || dp[i - 1][w];
20            // diagonal blue arrow in the above slides
21            // make sure current item's weight is smaller than the target weight w
22            if (w - weights[i - 1] >= 0) {
23                dp[i][w] = dp[i][w] || dp[i - 1][w - weights[i - 1]];
24            }
25        }
26    }
27    std::vector<int> ans;
28    // check the last row for all possible answers
29    for (int w = 0; w <= total_sum; w++) {
30        if (dp[n][w]) {
31            ans.emplace_back(w);
32        }
33    }
34    return ans;
35}
36
37template<typename T>
38std::vector<T> get_words() {
39    std::string line;
40    std::getline(std::cin, line);
41    std::istringstream ss{line};
42    ss >> std::boolalpha;
43    std::vector<T> v;
44    std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
45    return v;
46}
47
48template<typename T>
49void put_words(const std::vector<T>& v) {
50    if (!v.empty()) {
51        std::copy(v.begin(), std::prev(v.end()), std::ostream_iterator<T>{std::cout, " "});
52        std::cout << v.back();
53    }
54    std::cout << '\n';
55}
56
57int main() {
58    std::vector<int> weights = get_words<int>();
59    std::vector<int> res = knapsack_weight_only(weights);
60    std::sort(res.begin(), res.end());
61    put_words(res);
62}
63

The final runtime of this program is O(n * totalSum) because there is O(n * totalSum) states, each state depends on O(1) subproblems, and each state takes O(1) to compute.

Space Optimization (optional)

Finally, there is a slight memory optimization that we can perform. Observe that dp[i][w] depends on, at most, the previous row (dp[i][w] = dp[i][w] || dp[i - 1][w - weights[i - 1]]). Thus, instead of storing the entire 2D array, we can simply store two 1D arrays, one to keep track of the previous and one to for the current. This improves our memory usage from O(n * totalSum) to O(totalSum).

Here's the implementation:

1from typing import List
2
3def knapsack_weight_only(weights: List[int]) -> List[int]:
4    n = len(weights)
5    total_sum = sum(weights)  # get maximum sum possible
6
7    # initialize 2 1D arrays (2 * N array)
8    dp = [[False for _ in range(total_sum + 1)] for _ in range(2)]
9    dp[0][0] = True
10    for i in range(1, n + 1):
11        for w in range(total_sum + 1):
12            # current row is dp[1], previous row is dp[0]
13            dp[1][w] = dp[1][w] or dp[0][w]
14            if w - weights[i - 1] >= 0:
15                dp[1][w] = dp[1][w] or dp[0][w - weights[i - 1]]
16        for w in range(total_sum + 1):  # update previous row to current row
17            dp[0][w] = dp[1][w]
18
19    # dp[0][w] = true if `w` is an attainable weight, thus add it to our answer
20    ans: List[int] = []
21    for w in range(total_sum + 1):
22        if dp[0][w]:
23            ans.append(w)
24    return ans
25
26if __name__ == "__main__":
27    weights = [int(x) for x in input().split()]
28    res = knapsack_weight_only(weights)
29    print(" ".join(map(str, sorted(res))))
30

1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4import java.util.Scanner;
5import java.util.stream.Collectors;
6
7class Solution {
8    public static List<Integer> knapsackWeightOnly(List<Integer> weights) {
9        int n = weights.size();
10        int totalSum = 0; // get maximum sum possible
11        for (int weight : weights) {
12            totalSum += weight;
13        }
14
15        // initialize 2 1D arrays (2 * N array)
16        boolean[][] dp = new boolean[2][totalSum + 1];
17        dp[0][0] = true;
18        for (int i = 1; i <= n; i++) {
19            for (int w = 0; w <= totalSum; w++) {
20                // current row is dp[1], previous row is dp[0]
21                dp[1][w] = dp[1][w] || dp[0][w];
22                if (w - weights.get(i - 1) >= 0) {
23                    dp[1][w] = dp[1][w] || dp[0][w - weights.get(i - 1)];
24                }
25            }
26            for (int w = 0; w <= totalSum; w++) { // update previous row to current row
27                dp[0][w] = dp[1][w];
28            }
29        }
30        // dp[0][w] = true if `w` is an attainable weight, thus add it to our answer
31        List<Integer> ans = new ArrayList<>();
32        for (int w = 0; w <= totalSum; w++) {
33            if (dp[0][w]) {
34                ans.add(w);
35            }
36        }
37        return ans;
38    }
39
40    public static List<String> splitWords(String s) {
41        return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
42    }
43
44    public static void main(String[] args) {
45        Scanner scanner = new Scanner(System.in);
46        List<Integer> weights = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
47        scanner.close();
48        List<Integer> res = knapsackWeightOnly(weights);
49        System.out.println(res.stream().sorted().map(String::valueOf).collect(Collectors.joining(" ")));
50    }
51}
52

1#include <algorithm>
2#include <iostream>
3#include <iterator>
4#include <numeric>
5#include <sstream>
6#include <string>
7#include <vector>
8
9std::vector<int> knapsack_weight_only(std::vector<int>& weights) {
10    int n = weights.size();
11    int total_sum = std::accumulate(weights.begin(), weights.end(), 0);
12    std::vector<std::vector<bool>> dp(2, std::vector<bool>(total_sum + 1, false));
13    dp[0][0] = true;
14    for (int i = 1; i <= n; i++) {
15        for (int w = 0; w <= total_sum; w++) {
16            dp[1][w] = dp[1][w] || dp[0][w];
17            if (w - weights[i - 1] >= 0) {
18                dp[1][w] = dp[1][w] || dp[0][w - weights[i - 1]];
19            }
20        }
21        for (int w = 0; w <= total_sum; w++) { // update previous row to current row
22            dp[0][w] = dp[1][w];
23        }
24    }
25
26    // dp[0][w] = true if `w` is an attainable weight, thus add it to our answer
27    std::vector<int> ans;
28    for (int w = 0; w <= total_sum; w++) {
29        if (dp[0][w]) {
30            ans.emplace_back(w);
31        }
32    }
33    return ans;
34}
35
36template<typename T>
37std::vector<T> get_words() {
38    std::string line;
39    std::getline(std::cin, line);
40    std::istringstream ss{line};
41    ss >> std::boolalpha;
42    std::vector<T> v;
43    std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
44    return v;
45}
46
47template<typename T>
48void put_words(const std::vector<T>& v) {
49    if (!v.empty()) {
50        std::copy(v.begin(), std::prev(v.end()), std::ostream_iterator<T>{std::cout, " "});
51        std::cout << v.back();
52    }
53    std::cout << '\n';
54}
55
56int main() {
57    std::vector<int> weights = get_words<int>();
58    std::vector<int> res = knapsack_weight_only(weights);
59    std::sort(res.begin(), res.end());
60    put_words(res);
61}
62

The space optimization is a nice trick but it's also easy to get the row swapping wrong. It's great to mention this to the interviewer after you have perfected your regular solution and confirm that with the interviewer. Pre-mature optimization is the root of all evil in software engineering.

Steps to work through a DP problem:

We can see from this example the top-down and bottom-up are essentially equivalent.

Remember: DP = DFS + pruning + memoization.

Steps to solve a DP problem:

brute force
- draw the state-space tree
- dfs on the state-space tree
prune if possible
memo
- find the duplicate subtrees
bottom-up (if you want to)
- optional space optimzation