Поиск всех возможных комбинаций чисел для достижения заданной суммы

Question

Как бы вы провели тестирование всех возможных комбинаций дополнений из заданного набора чисел, чтобы они складывались до заданного конечного числа?

Пример:

• Набор чисел для добавления: {1,5,22,15,0, ...}
• Желаемый результат: 12345

Answer 1

Преобразование Swift 3 решения Java: (@JeremyThompson)

protocol _IntType { }
extension Int: _IntType {}


extension Array where Element: _IntType {

    func subsets(to: Int) -> [[Element]]? {

        func sum_up_recursive(_ numbers: [Element], _ target: Int, _ partial: [Element], _ solution: inout [[Element]]) {

            var sum: Int = 0
            for x in partial {
                sum += x as! Int
            }

            if sum == target {
                solution.append(partial)
            }

            guard sum < target else {
                return
            }

            for i in stride(from: 0, to: numbers.count, by: 1) {

                var remaining = [Element]()

                for j in stride(from: i + 1, to: numbers.count, by: 1) {
                    remaining.append(numbers[j])
                }

                var partial_rec = [Element](partial)
                partial_rec.append(numbers[i])

                sum_up_recursive(remaining, target, partial_rec, &solution)
            }
        }

        var solutions = [[Element]]()
        sum_up_recursive(self, to, [Element](), &solutions)

        return solutions.count > 0 ? solutions : nil
    }

}

использование:

let numbers = [3, 9, 8, 4, 5, 7, 10]

if let solution = numbers.subsets(to: 15) {
    print(solution) // output: [[3, 8, 4], [3, 5, 7], [8, 7], [5, 10]]
} else {
    print("not possible")
}

Answer 2

Версия PHP , вдохновленная версией Кейта Беллера на C #.

PHP-версия bala у меня не сработала, потому что мне не нужно было группировать числа. Я хотел более простую реализацию с одним целевым значением и пулом чисел. Эта функция также удалит любые повторяющиеся записи.

/**
 * Calculates a subset sum: finds out which combinations of numbers
 * from the numbers array can be added together to come to the target
 * number.
 * 
 * Returns an indexed array with arrays of number combinations.
 * 
 * Example: 
 * 
 * 
 * $matches = subset_sum(array(5,10,7,3,20), 25);
 * 

* * Возвращает: * *

 * Array
 * (
 *   [0] => Array
 *   (
 *       [0] => 3
 *       [1] => 5
 *       [2] => 7
 *       [3] => 10
 *   )
 *   [1] => Array
 *   (
 *       [0] => 5
 *       [1] => 20
 *   )
 * )
 * 

* * @param number [] $ numbers * @param number $ target * @param array $ part * @return array [number []] * / функция subset_sum ($ numbers, $ target, $ part = null) { // мы предполагаем, что пустая переменная $ part означает это // это вызов верхнего уровня. $ toplevel = false; if ($ part === null) { $ toplevel = true; $ part = array (); } $ s = 0; foreach ($ part как $ x) { $ s = $ s + $ x; } // мы нашли совпадение! если ($ s == $ target) { сортировать ($ часть); // убедитесь, что числа всегда отсортированы возвращаемый массив (implode ('|', $ part)); } // зашел слишком далеко, облом if ($ s> = $ target) { вернуть ноль; } $ match = array (); $ totalNumbers = count ($ numbers); для ($ i = 0; $ i

Answer 3

Я перенес образец C # в Objective-c и не увидел его в ответах:

//Usage
NSMutableArray* numberList = [[NSMutableArray alloc] init];
NSMutableArray* partial = [[NSMutableArray alloc] init];
int target = 16;
for( int i = 1; i<target; i++ )
{ [numberList addObject:@(i)]; }
[self findSums:numberList target:target part:partial];


//*******************************************************************
// Finds combinations of numbers that add up to target recursively
//*******************************************************************
-(void)findSums:(NSMutableArray*)numbers target:(int)target part:(NSMutableArray*)partial
{
    int s = 0;
    for (NSNumber* x in partial)
    { s += [x intValue]; }

    if (s == target)
    { NSLog(@"Sum[%@]", partial); }

    if (s >= target)
    { return; }

    for (int i = 0;i < [numbers count];i++ )
    {
        int n = [numbers[i] intValue];
        NSMutableArray* remaining = [[NSMutableArray alloc] init];
        for (int j = i + 1; j < [numbers count];j++)
        { [remaining addObject:@([numbers[j] intValue])]; }

        NSMutableArray* partRec = [[NSMutableArray alloc] initWithArray:partial];
        [partRec addObject:@(n)];
        [self findSums:remaining target:target part:partRec];
    }
}

Answer 4

Выведите 0 на первое место.Ноль является идентификатором сложения, поэтому он бесполезен по законам моноидов в данном конкретном случае.Также выведите отрицательные числа, если вы хотите подняться до положительного числа.В противном случае вам также потребуется операция вычитания.

Итак ... самый быстрый алгоритм, который вы можете получить на этой конкретной работе, заключается в следующем, приведенном в JS.

function items2T([n,...ns],t){
    var c = ~~(t/n);
    return ns.length ? Array(c+1).fill()
                                 .reduce((r,_,i) => r.concat(items2T(ns, t-n*i).map(s => Array(i).fill(n).concat(s))),[])
                     : t % n ? []
                             : [Array(c).fill(n)];
};

var data = [3, 9, 8, 4, 5, 7, 10],
    result;

console.time("combos");
result = items2T(data, 15);
console.timeEnd("combos");
console.log(JSON.stringify(result));

Это очень быстрый алгоритм, но если вы отсортируете массив data по убыванию , он будет еще быстрее.Использование .sort() незначительно, так как алгоритм в итоге будет иметь намного меньше рекурсивных вызовов.

Answer 5

@ Ответ КейтБеллера с немного измененными именами переменных и некоторыми комментариями.

    public static void Main(string[] args)
    {
        List<int> input = new List<int>() { 3, 9, 8, 4, 5, 7, 10 };
        int targetSum = 15;
        SumUp(input, targetSum);
    }

    public static void SumUp(List<int> input, int targetSum)
    {
        SumUpRecursive(input, targetSum, new List<int>());
    }

    private static void SumUpRecursive(List<int> remaining, int targetSum, List<int> listToSum)
    {
        // Sum up partial
        int sum = 0;
        foreach (int x in listToSum)
            sum += x;

        //Check sum matched
        if (sum == targetSum)
            Console.WriteLine("sum(" + string.Join(",", listToSum.ToArray()) + ")=" + targetSum);

        //Check sum passed
        if (sum >= targetSum)
            return;

        //Iterate each input character
        for (int i = 0; i < remaining.Count; i++)
        {
            //Build list of remaining items to iterate
            List<int> newRemaining = new List<int>();
            for (int j = i + 1; j < remaining.Count; j++)
                newRemaining.Add(remaining[j]);

            //Update partial list
            List<int> newListToSum = new List<int>(listToSum);
            int currentItem = remaining[i];
            newListToSum.Add(currentItem);
            SumUpRecursive(newRemaining, targetSum, newListToSum);
        }
    }'