# The number of all combinations in the Knapsack problem

There is the classic Knapsack problem . My version of this problem is slightly different.

Given a set of items, each with a weight, determine the number of combinations for packing items so that the total weight is less than or equal to the specified limit.

For example, there are five elements with weight: `1, 1, 3, 4, 5`

. Error with `limit = 7`

. The following combinations exist:

```
1 + 3
1 + 4
1 + 5
1 + 1 + 3
1 + 1 + 4
1 + 1 + 5
3
3 + 4
4
5
```

Is there a way to count the number of combinations without being rough?

source to share

This is one of the solutions:

```
items = [1,1,3,4,5]
knapsack = []
limit = 7
def print_solutions(current_item, knapsack, current_sum):
#if all items have been processed print the solution and return:
if current_item == len(items):
print knapsack
return
#don't take the current item and go check others
print_solutions(current_item + 1, list(knapsack), current_sum)
#take the current item if the value doesn't exceed the limit
if (current_sum + items[current_item] <= limit):
knapsack.append(items[current_item])
current_sum += items[current_item]
#current item taken go check others
print_solutions(current_item + 1, knapsack, current_sum )
print_solutions(0,knapsack,0)
```

** Prints:**

```
[]
[5]
[4]
[3]
[3, 4]
[1]
[1, 5]
[1, 4]
[1, 3]
[1]
[1, 5]
[1, 4]
[1, 3]
[1, 1]
[1, 1, 5]
[1, 1, 4]
[1, 1, 3]
```

source to share

** EACH ITEM USED UNLIMITED TIME**

This is a fairly simple **extension of the original problem** .

As you probably know, you are using DP to solve the original problem, where the element weights must be exactly W. When you are done with DP, you will also have a solution for all weights <W. To get your solution, **just summarize the** solutions for weights from 1 to W (and +1 for an empty set).

** EACH PART USED ONE**

In this case, there is no other way than the brute force of all possible combinations. This problem is NP-hard and will have time complexity O (2 ^ n).

To iterate over use the following code (borrowed from @pjsofts):

```
items = [1,1,3,4,5]
knapsack = []
limit = 7
def print_solutions(current_item, knapsack, current_sum):
#if all items have been processed print the solution and return:
if current_item == len(items):
print knapsack
return
#don't take the current item and go check others
print_solutions(current_item + 1, list(knapsack), current_sum)
#take the current item if the value doesn't exceed the limit
if (current_sum + items[current_item] <= limit):
knapsack.append(items[current_item])
current_sum += items[current_item]
#current item taken go check others
print_solutions(current_item + 1, knapsack, current_sum )
print_solutions(0,knapsack,0)
```

source to share

while others have posted some solutions, here is a translation of a naive extension of the problem using Haskell and simple recursion:

```
combinations :: Int -> [Int] -> [[Int]]
combinations _ [] = [[]]
combinations w (x:xs)
| w >= x = [ x:ys | ys <- combinations (w-x) xs] ++ combinations w xs
| otherwise = combinations w xs
```

### test run

```
λ> combinations 7 [5,4,3,1,1]
[[5,1,1],[5,1],[5,1],[5],[4,3],[4,1,1],[4,1],[4,1],[4],[3,1,1],[3,1],[3,1],[3],[1,1],[1],[1],[]]
```

### what's happening?

starting at 5, you have two options: either you accept it or you don't.

- If you do this, you have a constraint of 2 to the left and therefore you have to recursively search for how many ways to do it.
- if not, you still have a limit of 7, but only 1,1,3,4 to search ...

the algorithm translates this into basic Haskell with a reliable readable way - feel free to ask for details

## remarks

I haven't looked at performance at all, but it should be easy for you to do the same as with the original problem (rewrite table columns, ...)

source to share