Вопросы Теги

Печать всех подмножеств с заданной суммой [duplicate]

Regex движок Python не поддерживает эти; см. & sect; 7.2.1 «Синтаксис регулярного выражения» в документации Python для списка того, что он поддерживает . Однако вы можете получить тот же эффект, написав re.match(re.escape("bla"), "bla"); re.escape - функция, которая вставляет обратные косые черты перед всеми специальными символами.

Кстати, вы обычно должны использовать «сырые» строки r"..." вместо "...", так как в противном случае обратная косая черта будет обработана дважды (один раз, когда строка разбирается, а затем снова с помощью механизма регулярных выражений), что означает, что вы должны писать такие вещи, как \\b, а не \b. Использование r"..." предотвращает передачу первой обработки, поэтому вы можете просто написать \b.

173
задан Krish Munot 23 August 2016 в 06:13
поделиться

12 ответов

Эта проблема может быть решена с помощью рекурсивных комбинаций всех возможных сумм, отфильтровывающих те, которые достигают цели. Вот алгоритм в Python: 

def subset_sum(numbers, target, partial=[]):
    s = sum(partial)

    # check if the partial sum is equals to target
    if s == target: 
        print "sum(%s)=%s" % (partial, target)
    if s >= target:
        return  # if we reach the number why bother to continue

    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i+1:]
        subset_sum(remaining, target, partial + [n]) 


if __name__ == "__main__":
    subset_sum([3,9,8,4,5,7,10],15)

    #Outputs:
    #sum([3, 8, 4])=15
    #sum([3, 5, 7])=15
    #sum([8, 7])=15
    #sum([5, 10])=15

Этот тип алгоритмов очень хорошо объяснен в следующей лекции по теоретическому программированию в Standford - это видео очень рекомендуется для понимания того, как работает рекурсия для генерации перестановок решений.

Edit

Вышеупомянутая функция генератора, что делает ее более полезной. Требуется Python 3.3+ из-за yield from. 

def subset_sum(numbers, target, partial=[], partial_sum=0):
    if partial_sum == target:
        yield partial
    if partial_sum >= target:
        return
    for i, n in enumerate(numbers):
        remaining = numbers[i + 1:]
        yield from subset_sum(remaining, target, partial + [n], partial_sum + n)

Вот версия Java того же алгоритма: 

package tmp;

import java.util.ArrayList;
import java.util.Arrays;

class SumSet {
    static void sum_up_recursive(ArrayList<Integer> numbers, int target, ArrayList<Integer> partial) {
       int s = 0;
       for (int x: partial) s += x;
       if (s == target)
            System.out.println("sum("+Arrays.toString(partial.toArray())+")="+target);
       if (s >= target)
            return;
       for(int i=0;i<numbers.size();i++) {
             ArrayList<Integer> remaining = new ArrayList<Integer>();
             int n = numbers.get(i);
             for (int j=i+1; j<numbers.size();j++) remaining.add(numbers.get(j));
             ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial);
             partial_rec.add(n);
             sum_up_recursive(remaining,target,partial_rec);
       }
    }
    static void sum_up(ArrayList<Integer> numbers, int target) {
        sum_up_recursive(numbers,target,new ArrayList<Integer>());
    }
    public static void main(String args[]) {
        Integer[] numbers = {3,9,8,4,5,7,10};
        int target = 15;
        sum_up(new ArrayList<Integer>(Arrays.asList(numbers)),target);
    }
}

Это точно такая же эвристика. Моя Java немного ржавая, но я думаю, что ее легко понять.

Преобразование C # для решения Java: (byJJememyThompson) 

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

private static void sum_up(List<int> numbers, int target)
{
    sum_up_recursive(numbers, target, new List<int>());
}

private static void sum_up_recursive(List<int> numbers, int target, List<int> partial)
{
    int s = 0;
    foreach (int x in partial) s += x;

    if (s == target)
        Console.WriteLine("sum(" + string.Join(",", partial.ToArray()) + ")=" + target);

    if (s >= target)
        return;

    for (int i = 0; i < numbers.Count; i++)
    {
        List<int> remaining = new List<int>();
        int n = numbers[i];
        for (int j = i + 1; j < numbers.Count; j++) remaining.Add(numbers[j]);

        List<int> partial_rec = new List<int>(partial);
        partial_rec.Add(n);
        sum_up_recursive(remaining, target, partial_rec);
    }
}

Ruby Решение: (by @emaillenin) 

def subset_sum(numbers, target, partial=[])
  s = partial.inject 0, :+
# check if the partial sum is equals to target

  puts "sum(#{partial})=#{target}" if s == target

  return if s >= target # if we reach the number why bother to continue

  (0..(numbers.length - 1)).each do |i|
    n = numbers[i]
    remaining = numbers.drop(i+1)
    subset_sum(remaining, target, partial + [n])
  end
end

subset_sum([3,9,8,4,5,7,10],15)

Редактирование: обсуждение сложности

Как упоминают другие, это NP-трудная задача . Его можно решить в экспоненциальном времени O (2 ^ n), например, при n = 10 будет 1024 возможных решения. Если цели, которые вы пытаетесь достичь, находятся в низком диапазоне, этот алгоритм работает. Так, например:

subset_sum([1,2,3,4,5,6,7,8,9,10],100000) генерирует 1024 ветви, потому что цель никогда не пытается отфильтровать возможные решения.

С другой стороны, subset_sum([1,2,3,4,5,6,7,8,9,10],10) генерирует только 175 ветвей, поскольку цель для достижения 10 требуется отфильтровать многие комбинации.

Если N и Target - большие числа, следует перейти в примерную версию решения.

178
ответ дан user2357112 17 August 2018 в 13:18
поделиться
  • 1
    Оптимизация Java: ArrayList & lt; Integer & gt; partial_rec = new ArrayList & lt; Integer & gt; (partial); partial_rec.add (п); это делает копию частичного. и, таким образом, добавляет O (N). Лучший способ - просто "partial.add (n)" выполните рекурсию, а затем «partial.remove» (partial.size -1). Я переработал ваш код, чтобы убедиться. Он отлично работает – Christian Bongiorno 20 April 2015 в 00:10
  • 2
    Это решение не работает для всех случаев. Рассмотрим [1, 2, 0, 6, -3, 3], 3 - он выводит только [1,2], [0,3], [3], а отсутствующие случаи, такие как [6, -3, 3] – LiraNuna 11 March 2016 в 20:25
  • 3
    Он также не работает для каждой комбинации, например [1, 2, 5], 5 только выходы [5], когда [1, 1, 1, 1, 1], [2, 2, 1] и [2, 1, 1, 1] являются решениями. – cbrad 10 June 2016 в 23:18
  • 4
    @cbrad, что из-за i+1 в remaining = numbers[i+1:]. Похоже, что этот алгоритм не позволяет дублировать. – Leonid Vasilev 8 May 2018 в 09:16
  • 5
    @cbrad Чтобы получить также решения, включая дубликаты, такие как [1, 1, 3], посмотрите stackoverflow.com/a/34971783/3684296 (Python) – Mesa 25 May 2018 в 20:17

нерекурсивная версия Java, которая просто добавляет элементы и перераспределяет их между возможными значениями. 0 'игнорируются и работают для фиксированных списков (то, что вам дано, это то, с чем вы можете играть) или список повторяемых чисел. 

import java.util.*;

public class TestCombinations {

    public static void main(String[] args) {
        ArrayList<Integer> numbers = new ArrayList<>(Arrays.asList(0, 1, 2, 2, 5, 10, 20));
        LinkedHashSet<Integer> targets = new LinkedHashSet<Integer>() {{
            add(4);
            add(10);
            add(25);
        }};

        System.out.println("## each element can appear as many times as needed");
        for (Integer target: targets) {
            Combinations combinations = new Combinations(numbers, target, true);
            combinations.calculateCombinations();
            for (String solution: combinations.getCombinations()) {
                System.out.println(solution);
            }
        }

        System.out.println("## each element can appear only once");
        for (Integer target: targets) {
            Combinations combinations = new Combinations(numbers, target, false);
            combinations.calculateCombinations();
            for (String solution: combinations.getCombinations()) {
                System.out.println(solution);
            }
        }
    }

    public static class Combinations {
        private boolean allowRepetitions;
        private int[] repetitions;
        private ArrayList<Integer> numbers;
        private Integer target;
        private Integer sum;
        private boolean hasNext;
        private Set<String> combinations;

        /**
         * Constructor.
         *
         * @param numbers Numbers that can be used to calculate the sum.
         * @param target  Target value for sum.
         */
        public Combinations(ArrayList<Integer> numbers, Integer target) {
            this(numbers, target, true);
        }

        /**
         * Constructor.
         *
         * @param numbers Numbers that can be used to calculate the sum.
         * @param target  Target value for sum.
         */
        public Combinations(ArrayList<Integer> numbers, Integer target, boolean allowRepetitions) {
            this.allowRepetitions = allowRepetitions;
            if (this.allowRepetitions) {
                Set<Integer> numbersSet = new HashSet<>(numbers);
                this.numbers = new ArrayList<>(numbersSet);
            } else {
                this.numbers = numbers;
            }
            this.numbers.removeAll(Arrays.asList(0));
            Collections.sort(this.numbers);

            this.target = target;
            this.repetitions = new int[this.numbers.size()];
            this.combinations = new LinkedHashSet<>();

            this.sum = 0;
            if (this.repetitions.length > 0)
                this.hasNext = true;
            else
                this.hasNext = false;
        }

        /**
         * Calculate and return the sum of the current combination.
         *
         * @return The sum.
         */
        private Integer calculateSum() {
            this.sum = 0;
            for (int i = 0; i < repetitions.length; ++i) {
                this.sum += repetitions[i] * numbers.get(i);
            }
            return this.sum;
        }

        /**
         * Redistribute picks when only one of each number is allowed in the sum.
         */
        private void redistribute() {
            for (int i = 1; i < this.repetitions.length; ++i) {
                if (this.repetitions[i - 1] > 1) {
                    this.repetitions[i - 1] = 0;
                    this.repetitions[i] += 1;
                }
            }
            if (this.repetitions[this.repetitions.length - 1] > 1)
                this.repetitions[this.repetitions.length - 1] = 0;
        }

        /**
         * Get the sum of the next combination. When 0 is returned, there's no other combinations to check.
         *
         * @return The sum.
         */
        private Integer next() {
            if (this.hasNext && this.repetitions.length > 0) {
                this.repetitions[0] += 1;
                if (!this.allowRepetitions)
                    this.redistribute();
                this.calculateSum();

                for (int i = 0; i < this.repetitions.length && this.sum != 0; ++i) {
                    if (this.sum > this.target) {
                        this.repetitions[i] = 0;
                        if (i + 1 < this.repetitions.length) {
                            this.repetitions[i + 1] += 1;
                            if (!this.allowRepetitions)
                                this.redistribute();
                        }
                        this.calculateSum();
                    }
                }

                if (this.sum.compareTo(0) == 0)
                    this.hasNext = false;
            }
            return this.sum;
        }

        /**
         * Calculate all combinations whose sum equals target.
         */
        public void calculateCombinations() {
            while (this.hasNext) {
                if (this.next().compareTo(target) == 0)
                    this.combinations.add(this.toString());
            }
        }

        /**
         * Return all combinations whose sum equals target.
         *
         * @return Combinations as a set of strings.
         */
        public Set<String> getCombinations() {
            return this.combinations;
        }

        @Override
        public String toString() {
            StringBuilder stringBuilder = new StringBuilder("" + sum + ": ");
            for (int i = 0; i < repetitions.length; ++i) {
                for (int j = 0; j < repetitions[i]; ++j) {
                    stringBuilder.append(numbers.get(i) + " ");
                }
            }
            return stringBuilder.toString();
        }
    }
}

Пример ввода: 

numbers: 0, 1, 2, 2, 5, 10, 20
targets: 4, 10, 25

Выход образца: 

## each element can appear as many times as needed
4: 1 1 1 1 
4: 1 1 2 
4: 2 2 
10: 1 1 1 1 1 1 1 1 1 1 
10: 1 1 1 1 1 1 1 1 2 
10: 1 1 1 1 1 1 2 2 
10: 1 1 1 1 2 2 2 
10: 1 1 2 2 2 2 
10: 2 2 2 2 2 
10: 1 1 1 1 1 5 
10: 1 1 1 2 5 
10: 1 2 2 5 
10: 5 5 
10: 10 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 
25: 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 
25: 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 
25: 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 
25: 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 
25: 1 1 1 2 2 2 2 2 2 2 2 2 2 2 
25: 1 2 2 2 2 2 2 2 2 2 2 2 2 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 5 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 5 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 5 
25: 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 5 
25: 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 5 
25: 1 1 1 1 1 1 1 1 2 2 2 2 2 2 5 
25: 1 1 1 1 1 1 2 2 2 2 2 2 2 5 
25: 1 1 1 1 2 2 2 2 2 2 2 2 5 
25: 1 1 2 2 2 2 2 2 2 2 2 5 
25: 2 2 2 2 2 2 2 2 2 2 5 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 5 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 2 5 5 
25: 1 1 1 1 1 1 1 1 1 1 1 2 2 5 5 
25: 1 1 1 1 1 1 1 1 1 2 2 2 5 5 
25: 1 1 1 1 1 1 1 2 2 2 2 5 5 
25: 1 1 1 1 1 2 2 2 2 2 5 5 
25: 1 1 1 2 2 2 2 2 2 5 5 
25: 1 2 2 2 2 2 2 2 5 5 
25: 1 1 1 1 1 1 1 1 1 1 5 5 5 
25: 1 1 1 1 1 1 1 1 2 5 5 5 
25: 1 1 1 1 1 1 2 2 5 5 5 
25: 1 1 1 1 2 2 2 5 5 5 
25: 1 1 2 2 2 2 5 5 5 
25: 2 2 2 2 2 5 5 5 
25: 1 1 1 1 1 5 5 5 5 
25: 1 1 1 2 5 5 5 5 
25: 1 2 2 5 5 5 5 
25: 5 5 5 5 5 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10 
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 2 10 
25: 1 1 1 1 1 1 1 1 1 1 1 2 2 10 
25: 1 1 1 1 1 1 1 1 1 2 2 2 10 
25: 1 1 1 1 1 1 1 2 2 2 2 10 
25: 1 1 1 1 1 2 2 2 2 2 10 
25: 1 1 1 2 2 2 2 2 2 10 
25: 1 2 2 2 2 2 2 2 10 
25: 1 1 1 1 1 1 1 1 1 1 5 10 
25: 1 1 1 1 1 1 1 1 2 5 10 
25: 1 1 1 1 1 1 2 2 5 10 
25: 1 1 1 1 2 2 2 5 10 
25: 1 1 2 2 2 2 5 10 
25: 2 2 2 2 2 5 10 
25: 1 1 1 1 1 5 5 10 
25: 1 1 1 2 5 5 10 
25: 1 2 2 5 5 10 
25: 5 5 5 10 
25: 1 1 1 1 1 10 10 
25: 1 1 1 2 10 10 
25: 1 2 2 10 10 
25: 5 10 10 
25: 1 1 1 1 1 20 
25: 1 1 1 2 20 
25: 1 2 2 20 
25: 5 20 
## each element can appear only once
4: 2 2 
10: 1 2 2 5 
10: 10 
25: 1 2 2 20 
25: 5 20
2
ответ дан Bernat 17 August 2018 в 13:18
поделиться

Рекомендуется в качестве ответа:

Вот решение, использующее генераторы es2015 : 

function* subsetSum(numbers, target, partial = [], partialSum = 0) {

  if(partialSum === target) yield partial

  if(partialSum >= target) return

  for(let i = 0; i < numbers.length; i++){
    const remaining = numbers.slice(i + 1)
        , n = numbers[i]

    yield* subsetSum(remaining, target, [...partial, n], partialSum + n)
  }

}

Использование генераторов действительно может быть очень полезным, поскольку оно позволяет вам чтобы приостановить выполнение скрипта сразу после нахождения действительного подмножества. Это контрастирует с решениями без генераторов (т. Е. С отсутствием состояния), которым приходится проходить через каждое подмножество numbers

0
ответ дан feihcsim 17 August 2018 в 13:18
поделиться

Найти комбинации с помощью excel - (довольно легко). (Ваш компьютер не должен быть слишком медленным)

  1. Перейти на сайт
  2. Перейти на страницу «Сумма к цели»
  3. Загрузите файл excel для Sum to Target. Следуйте указаниям на странице веб-сайта.

надеюсь, что это поможет.

2
ответ дан Mario Sannum 17 August 2018 в 13:18
поделиться

Вот решение в R 

subset_sum = function(numbers,target,partial=0){
  if(any(is.na(partial))) return()
  s = sum(partial)
  if(s == target) print(sprintf("sum(%s)=%s",paste(partial[-1],collapse="+"),target))
  if(s > target) return()
  for( i in seq_along(numbers)){
    n = numbers[i]
    remaining = numbers[(i+1):length(numbers)]
    subset_sum(remaining,target,c(partial,n))
  }
}
1
ответ дан Mark 17 August 2018 в 13:18
поделиться

Версия Javascript: 

function subsetSum(numbers, target, partial) {
  var s, n, remaining;

  partial = partial || [];

  // sum partial
  s = partial.reduce(function (a, b) {
    return a + b;
  }, 0);

  // check if the partial sum is equals to target
  if (s === target) {
    console.log("%s=%s", partial.join("+"), target)
  }

  if (s >= target) {
    return;  // if we reach the number why bother to continue
  }

  for (var i = 0; i < numbers.length; i++) {
    n = numbers[i];
    remaining = numbers.slice(i + 1);
    subsetSum(remaining, target, partial.concat([n]));
  }
}

subsetSum([3,9,8,4,5,7,10],15);

// output:
// 3+8+4=15
// 3+5+7=15
// 8+7=15
// 5+10=15

20
ответ дан rbarilani 17 August 2018 в 13:18
поделиться

Решение этой проблемы было дано миллион раз в Интернете. Задача называется Задача об изменении монет . Можно найти решения в http://rosettacode.org/wiki/Count_the_coins и математическую модель этого в http://jaqm.ro/issues/volume-5,issue-2/ pdf / patterson_harmel.pdf (или проблема с изменением монеты Google ).

Кстати, решение Scala от Tsagadai интересно. В этом примере получается 1 или 0. В качестве побочного эффекта он перечисляет на консоли все возможные решения. Он отображает решение, но не делает его пригодным для использования каким-либо образом.

Чтобы быть как можно полезнее, код должен возвращать List[List[Int]], чтобы разрешить получать количество решений (длина списка списков), «лучшее» решение (самый короткий список) или все возможные решения.

Вот пример. Это очень неэффективно, но это легко понять. 

object Sum extends App {

  def sumCombinations(total: Int, numbers: List[Int]): List[List[Int]] = {

    def add(x: (Int, List[List[Int]]), y: (Int, List[List[Int]])): (Int, List[List[Int]]) = {
      (x._1 + y._1, x._2 ::: y._2)
    }

    def sumCombinations(resultAcc: List[List[Int]], sumAcc: List[Int], total: Int, numbers: List[Int]): (Int, List[List[Int]]) = {
      if (numbers.isEmpty || total < 0) {
        (0, resultAcc)
      } else if (total == 0) {
        (1, sumAcc :: resultAcc)
      } else {
        add(sumCombinations(resultAcc, sumAcc, total, numbers.tail), sumCombinations(resultAcc, numbers.head :: sumAcc, total - numbers.head, numbers))
      }
    }

    sumCombinations(Nil, Nil, total, numbers.sortWith(_ > _))._2
  }

  println(sumCombinations(15, List(1, 2, 5, 10)) mkString "\n")
}

При запуске он отображает: 

List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2)
List(1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2)
List(1, 1, 1, 1, 1, 2, 2, 2, 2, 2)
List(1, 1, 1, 2, 2, 2, 2, 2, 2)
List(1, 2, 2, 2, 2, 2, 2, 2)
List(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5)
List(1, 1, 1, 1, 1, 1, 1, 1, 2, 5)
List(1, 1, 1, 1, 1, 1, 2, 2, 5)
List(1, 1, 1, 1, 2, 2, 2, 5)
List(1, 1, 2, 2, 2, 2, 5)
List(2, 2, 2, 2, 2, 5)
List(1, 1, 1, 1, 1, 5, 5)
List(1, 1, 1, 2, 5, 5)
List(1, 2, 2, 5, 5)
List(5, 5, 5)
List(1, 1, 1, 1, 1, 10)
List(1, 1, 1, 2, 10)
List(1, 2, 2, 10)
List(5, 10)

Функция sumCombinations() может использоваться сама по себе и результат может быть дополнительно проанализирован, чтобы отобразить «лучшее» решение (самый короткий список) или количество решений (количество списков).

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

Например, мы могли бы подумать, что List(5, 10) должен дать две комбинации: List(5, 10) и List(10, 5). Для List(5, 5, 5) он может давать только три комбинации или один, в зависимости от требований. Для целых чисел три перестановки эквивалентны, но если мы имеем дело с монетами, например, в «проблеме смены монет», это не так.

Также не указано в требованиях, является ли вопрос о том, (или монету) можно использовать только один или несколько раз. Мы могли бы (и должны!) Обобщить проблему на список списков вхождений каждого числа. Это переводит в реальной жизни в «каковы возможные способы сделать определенную сумму денег с помощью набора монет (а не набора значений монет)». Первоначальная проблема - только частный случай этого, где у нас столько же вхождений каждой монеты, сколько необходимо, чтобы сделать общую сумму с каждым значением одной монеты.

23
ответ дан Rodrigue 17 August 2018 в 13:18
поделиться
  • 1
    Эта проблема не совсем такая же, как проблема с изменением монет. ОП запрашивает всю комбинацию, а не только минимальную. И, предположительно, целые числа в множестве могут быть отрицательными. Следовательно, некоторые оптимизации проблемы с изменением монет невозможно с этой проблемой. – ThomasMcLeod 20 March 2013 в 16:24
  • 2
    а также эта проблема позволяет повторять элементы, я не уверен, что OP хотел этого, но больше проблема с рюкзаком – caub 25 March 2014 в 16:16

Преобразование Java в Swift 3: (by @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")
}
1
ответ дан RolandasR 17 August 2018 в 13:18
поделиться

Другим решением для python будет использование модуля itertools.combinations следующим образом: 

#!/usr/local/bin/python

from itertools import combinations

def find_sum_in_list(numbers, target):
    results = []
    for x in range(len(numbers)):
        results.extend(
            [   
                combo for combo in combinations(numbers ,x)  
                    if sum(combo) == target
            ]   
        )   

    print results

if __name__ == "__main__":
    find_sum_in_list([3,9,8,4,5,7,10], 15)

Выход: [(8, 7), (5, 10), (3, 8, 4), (3, 5, 7)]

3
ответ дан Sebastian Palma 17 August 2018 в 13:18
поделиться

Версия 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: 
 * 
 * <pre>
 * $matches = subset_sum(array(5,10,7,3,20), 25);
 * </pre>
 * 
 * Returns:
 * 
 * <pre>
 * Array
 * (
 *   [0] => Array
 *   (
 *       [0] => 3
 *       [1] => 5
 *       [2] => 7
 *       [3] => 10
 *   )
 *   [1] => Array
 *   (
 *       [0] => 5
 *       [1] => 20
 *   )
 * )
 * </pre>
 * 
 * @param number[] $numbers
 * @param number $target
 * @param array $part
 * @return array[number[]]
 */
function subset_sum($numbers, $target, $part=null)
{
    // we assume that an empty $part variable means this
    // is the top level call.
    $toplevel = false;
    if($part === null) {
        $toplevel = true;
        $part = array();
    }

    $s = 0;
    foreach($part as $x) 
    {
        $s = $s + $x;
    }

    // we have found a match!
    if($s == $target) 
    {
        sort($part); // ensure the numbers are always sorted
        return array(implode('|', $part));
    }

    // gone too far, break off
    if($s >= $target) 
    {
        return null;
    }

    $matches = array();
    $totalNumbers = count($numbers);

    for($i=0; $i < $totalNumbers; $i++) 
    {
        $remaining = array();
        $n = $numbers[$i];

        for($j = $i+1; $j < $totalNumbers; $j++) 
        {
            $remaining[] = $numbers[$j];
        }

        $part_rec = $part;
        $part_rec[] = $n;

        $result = subset_sum($remaining, $target, $part_rec);
        if($result) 
        {
            $matches = array_merge($matches, $result);
        }
    }

    if(!$toplevel) 
    {
        return $matches;
    }

    // this is the top level function call: we have to
    // prepare the final result value by stripping any
    // duplicate results.
    $matches = array_unique($matches);
    $result = array();
    foreach($matches as $entry) 
    {
        $result[] = explode('|', $entry);
    }

    return $result;
}
29
ответ дан smac89 17 August 2018 в 13:18
поделиться
  • 1
    Вау, это довольно краткий код. Я в порядке с вашим ответом. Думаю, мне просто нужно немного почитать алгоритмы в целом. Я посмотрю на синтаксис двух языков, поскольку вы вызвали мое любопытство. – James P. 14 January 2011 в 09:44
  • 2
    Я только что установил Haskell, чтобы попробовать это, определенно не могу просто вставить его и выполнить, not in scope: 'subsequences' любые указатели? – Hart CO 6 February 2014 в 23:36
  • 3
    @HartCO немного опоздал на вечеринку, но import Data.List – Jir 14 August 2016 в 14:17
  • 4
    всем привет! Мне нужен код, чтобы сделать что-то подобное, найти все возможные суммы наборов из 6 чисел в списке из 60 чисел. Суммы должны быть в диапазоне min 180, max 191. Может ли этот код быть скорректирован для этого? Где запускать этот код в облаке? Я не добился успеха в Codenvy – Lorenco Gonzaga 20 September 2016 в 19:38
29
ответ дан smac89 6 September 2018 в 09:24
поделиться
29
ответ дан smac89 29 October 2018 в 15:57
поделиться
Другие вопросы по тегам:

Похожие вопросы: