Excel: Find a subset of numbers that add to a given total?

I have a column of numbers (lets say it's A1:A100) and I need to find a subset of them that sum to a certain total.

Solution 1:

It's possible with the Solver add-in*. The following steps worked for me in Excel 2007 and 2010.

1. Designate a cell to hold the result (C1 for this example) - this is the target cell, and a column that excel can use for scratch-work (B1:B100 for this example)
2. In the target cell, enter the formula "=SUMPRODUCT(A1:A100,B1:B100)" (no quotes). This will calculate the sum of A1*B1+A2*B2+...etc
3. Select Open the solver (Data tab, Analysis group)
4. The target cell should be obvious ($C$1 for this example)
5. For 'Equal To:' select 'Value of:' and enter the desired value
6. In the 'By Changing Cells' enter "$B$1:$B$100" (no quotes, and it may be necessary to initialize these values to 0 yourself)
7. Add a constraint to the cells that can be changed. In the pull-down, select 'bin' (Binary). This restricts the values of these cells to 0 (removing the corresponding A cell from the sum) or 1 (adding the corresponding A cell to the sum).
8. Click 'Solve' and wait. The numbers that are part of the subset you're looking for will have a 1 in the B column

If the solver is taking a long time, you can help it out by removing rows that obviously won't work (total is in dollars, and only one row has nonzero cents)

Bonus: You can have excel automatically highlight the cells that you're looking for by adding conditional formatting to those cells. Select all of the cells you want to format and from (Home tab)>>(Styles group)>>Conditional formatting>>New Rule select 'Use a formula to determine which cells to format'. In the formula, enter '=$B1=1' (no quotes) which will evaluate to true if the corresponding row in the B column is 1. For the format, you can add whatever you want (bold, italic, green fill, etc).

Another easy way to find the important rows is to sort column B Z->A, and all the 1's will come to the top.

*The solver add-in can be installed with these steps

1. Click the Microsoft Office Button, and then click Excel Options.
2. Click Add-Ins, and then in the Manage box, select Excel Add-ins.
3. Click Go.
4. In the Add-Ins available box, select the Solver Add-in check box, and then click OK. (If Solver Add-in is not listed in the Add-Ins available box, click Browse to locate the add-in.)
5. If you get prompted that the Solver Add-in is not currently installed on your computer, click Yes to install it.

Solution 2:

There is a low cost Excel Add-in SumMatch, which will highlight the subset of numbers that add up to a target sum.