Why canâ€™t you solve this problem like this, wonâ€™t this get the same runtime O(n*total_sum) but the code is more clean:

def knapsack_weight_only(weights: List[int]) â†’ List[int]:

res = set([0])

for num in weights:

cur_sums = []

for sum_ in res:

if num+sum_ not in res:

cur_sums.append(num+sum_)

res.update(cur_sums)

return list(res)

The solution is so unoptimal, why would you use vectors with total_sum lengths each? Imagine if you have 100 numbers with values about 10M in that case the length of vectors should be about 1B and you need a loop 1B times! The right approach is to use set of sums combinable with 0-i weights and the number of elements of that set would be doubled on each step in worst case so we have time complexity O(2^n) in worst case. Though it even worse for silly vector with total_sum length

In the main function, instead of printing System.out.print(i), it needs to be printing System.out.print(res.get(i))

I changed it and solution is correct now. May just want to change that to show by default.

Love this platform, keep it up

C# output mismatch on equal results and last line in main should join res instead of row

Updated, thanks!

Updated, thanks!

Grad youâ€™re enjoying the platform

Still see an old one.

Hi Vladislav, I meant itâ€™ll be included in the next deployment

@mod `memo`

is not getting updated in memoized version of `generate_sums`

function.

Anyone having issues with the tester? the output is not actually whats returned from the code. I tried copying the solution and running the tester, and it failed too.

Why isnt there an option to see the solution in the â€śTry-it-yourselfâ€ť portion?

Isnâ€™t this a strictly better solution?

def knapsack_weight_only(weights: List[int]) â†’ List[int]:

dp = set([0])

```
for weight in weights:
for currentWeight in list(dp):
dp.add(currentWeight + weight)
return list(dp)
```

Problems with multiple solutions currently do not have one-click solution loading function.

created github issue https://github.com/realAlgoMonster/contrib/issues/66 to cleanup topdown solution - just in case anyoneâ€™s top down solution is not working.

JS Bottom-Up solution with space optimization

```
function knapsackWeightOnly(weights) {
const n = weights.length;
const totalSum = weights.reduce((sum, weight) => sum + weight, 0);
const dp = Array.from(
{ length: 2 },
() => Array(totalSum + 1).fill(false)
);
dp[0][0] = true;
for (let i = 1; i <= n; i++) {
for (let w = 0; w <= totalSum; w++) {
dp[1][w] = dp[1][w] || dp[0][w];
if (w >= weights[i - 1]) {
dp[1][w] = dp[1][w] || dp[0][w - weights[i - 1]];
}
}
for (let w = 0; w <= totalSum; w++) {
dp[0][w] = dp[1][w];
}
}
const result = [];
for (let w = 0; w <= totalSum; w++) {
if (dp[0][w]) result.push(w);
}
return result;
}
```

For the python bottom up solution:

Line 11: what is the current itemâ€™s weight (w[i-1]), and what is the target weight (w), as in why are they called current item and target? I donâ€™t understand what the check does.

Thank you so much.

For the python bottom up solution:

Line 11: what is the current itemâ€™s weight (w[i-1]), and what is the target weight (w), as in why are they called current item and target? I donâ€™t understand what the check does.

Thank you so much.

To me, using Set with custom class to record visited node is much easier to understand.

Here is a Java example:

private static class Coordinate{

int x;

int y;

```
public Coordinate(int xValue, int yValue) {
this.x = xValue;
this.y = yValue;
}
@Override
public int hashCode() {
return x + y;
}
@Override
public boolean equals(Object obj) {
if (obj == null) return false;
Coordinate coordinate = (Coordinate)obj;
return (coordinate.x == x && coordinate.y == y);
}
}
public static List<Integer> knapsackWeightOnly(List<Integer> weights) {
List<Integer>answer = new ArrayList<>();
Set<Integer>set = new HashSet<>();
Set<Coordinate>visited = new HashSet<>();
answer.add(0);
set.add(0);
dfs(answer, weights, set, visited, 0, 0);
return answer;
}
private static void dfs(List<Integer>answer, List<Integer> weights, Set<Integer>set, Set<Coordinate>visited,
int index, int sum) {
Coordinate coordinate = new Coordinate(index, sum);
if (visited.contains(coordinate)) return;
if (index == weights.size()) {
if (!set.contains(sum)) {
set.add(sum);
answer.add(sum);
}
return;
}
int next = sum + weights.get(index);
dfs(answer, weights, set, visited, index + 1, next);
next = sum;
dfs(answer, weights, set, visited, index + 1, next);
visited.add(coordinate);
}
```

I simplified the last version of the solution in a way that made it easier for me to understand the approach. Hope you find it useful.

std::vector knapsack_weight_only(std::vector weights) {

int totalSum = accumulate(weights.begin(), weights.end(), 0);

int size = weights.size();

vector<vector> dp(2, vector(totalSum + 1, false));

dp[0][0] = true;

dp[1][0] = true;

for (int i = 1; i <= size; i++) {

for (int w = 0; w <= totalSum; w++) {

if (w - weights[i - 1] >= 0) {

dp[1][w] = dp[1][w] || dp[0][w - weights[i - 1]];

}

}

```
dp[0] = dp[1];
}
vector<int> ans;
for (int w = 0; w <= totalSum; w++) {
if (dp[1][w]) {
ans.push_back(w);
}
}
return ans;
```

}