Я нахожу функцию, в которой этот пара имеет *, например func (a, b, *, c = 1), что означает? [Дубликат]

Эта проблема может быть решена с помощью рекурсивных комбинаций всех возможных сумм, отфильтровывающих те, которые достигают цели. Вот алгоритм в 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 numbers, int target, ArrayList 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 remaining = new ArrayList();
             int n = numbers.get(i);
             for (int j=i+1; j partial_rec = new ArrayList(partial);
             partial_rec.add(n);
             sum_up_recursive(remaining,target,partial_rec);
       }
    }
    static void sum_up(ArrayList numbers, int target) {
        sum_up_recursive(numbers,target,new ArrayList());
    }
    public static void main(String args[]) {
        Integer[] numbers = {3,9,8,4,5,7,10};
        int target = 15;
        sum_up(new ArrayList(Arrays.asList(numbers)),target);
    }
}

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

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

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

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

private static void sum_up_recursive(List numbers, int target, List 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 remaining = new List();
        int n = numbers[i];
        for (int j = i + 1; j < numbers.Count; j++) remaining.Add(numbers[j]);

        List partial_rec = new List(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 - большие числа, следует перейти в примерную версию решения.