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.

Trivia: This is an instance of a NPcomplete problem: en.wikipedia.org/wiki/Subset_sum_problem– Dave L.Mar 4, 2016 at 1:03
2 Answers
It's possible with the Solver addin*. The following steps worked for me in Excel 2007 and 2010.
 Designate a cell to hold the result (C1 for this example)  this is the target cell, and a column that excel can use for scratchwork (B1:B100 for this example)
 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
 Select Open the solver (Data tab, Analysis group)
 The target cell should be obvious ($C$1 for this example)
 For 'Equal To:' select 'Value of:' and enter the desired value
 In the 'By Changing Cells' enter "$B$1:$B$100" (no quotes, and it may be necessary to initialize these values to 0 yourself)
 Add a constraint to the cells that can be changed. In the pulldown, 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).
 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 addin can be installed with these steps
 Click the Microsoft Office Button, and then click Excel Options.
 Click AddIns, and then in the Manage box, select Excel Addins.
 Click Go.
 In the AddIns available box, select the Solver Addin check box, and then click OK. (If Solver Addin is not listed in the AddIns available box, click Browse to locate the addin.)
 If you get prompted that the Solver Addin is not currently installed on your computer, click Yes to install it.

1In Excel 2013 you need to uncheck "Ignore Integer Constraints" from the options menu. Otherwise you get non INT values for 0 and 1 Jul 30, 2013 at 14:44

1In order to make this work properly: 1. The formula in Cell C1 should be sumPRODUCT (not just sum) 2. The cells in Column B should all have zero input in them.– user268218Oct 30, 2013 at 18:18

Thanks! For me, the old steps still work, but I like sumproduct better because it doesn't rely on the array formulas feature. Oct 30, 2013 at 23:52

anyway to find all the combinations... although there is one solution found by solver.. how to find the other solutions??? my array is here: v = [1100, 1105, 11830, 14790, 2325, 2455, 2555, 2935, 3050, 3150, 3185, 3370, 3475, 350, 3530, 3590, 3680, 3745, 885, 9624] sum = 43029... solution1 = [350, 1100, 2325, 2455, 2555, 2935, 3150, 3745, 9624, 14790], solution2 = [350, 885, 1100, 1105, 2325, 2455, 2555, 3530, 3590, 3680, 9624, 11830] Jul 8, 2015 at 8:09
There is a low cost Excel Addin SumMatch, which will highlight the subset of numbers that add up to a target sum.

1Hello AIsoft, good find. Maybe next time you can add some more information.– nixdaDec 30, 2012 at 3:24

@pnuts Did I made mistake? I don't understand what you mean with AUD$30– nixdaDec 30, 2012 at 3:41


6Note for myself: AUD$30 = 30 australian US Dollar. Its not a reference to an Excel cell [AUD30] with a fixed column.... :D– nixdaDec 30, 2012 at 5:32

1The price tag is a drawback, as is the lack of clear instructions. Anything more than 1 sentence + 1 picture from the product's website, really. Jan 9, 2013 at 21:53