C# algorithm - listing all permutations of number

This is sort of a follow up to a question I posted earlier (C# algorithm - find least number of objects necessary), but a bit different.

Given I have the following code:

var max = 80;
var list = new[]{10,20,30,40,50, 60);

I want to generate a array containing all the possible combinations I can use those numbers 开发者_如何学编程in the list to get to that max number.

The array would contain, {40, 40}, {50, 30}, {40,30, 10} etc...

You'll want to iterate over all the numbers in descending order. Then recursively add each next descending number in the sequence. Each time the sum matches, note that combo, pop out, and move on. When your tentative sum takes you over the max variable, pop out of the function to the next function in the stack. If the max still hasn't been reached, successively add the next number down in the sequence. In this way you will cover ever possible sequence, with no duplicates (unless there are duplicates in the given set, in which case you would want that duplicate). It will be not too much code actually.

The naive approach is to simply generate every combination of numbers possible, and see if they add up to the target number.

Needless to say, this has hideous time complexity. But it does the job for small lists.

EDIT: Actually, if you're allowing repeated numbers, this doesn't work. An alternative algorithm (which allows repeats, but not any negatives) is to basically keep adding up the highest number in the list, and then backtrack if you go over the target.