您将如何测试一组给定数字的加法的所有可能组合,以便将它们累加到给定的最终数字?
例:
可以通过将所有可能的总和的递归组合滤除掉达到目标的总和来解决此问题。这是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的Abstract Programming演讲中,很好地解释了这种算法-该视频非常可取,以了解递归如何工作以生成解的置换。
编辑
上面作为生成器函数,使其更加有用。由于,需要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有点生锈,但我认为它很容易理解。
Java解决方案的C#转换:( 通过@JeremyThompson)
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解决方案: (@ 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
是大数字,则应进入解决方案的近似版本。
Java优化:ArrayList <Integer> partial_rec = new ArrayList <Integer>(partial); partial_rec.add(n); 这会做部分副本。并因此加上O(N)。更好的方法是仅“ partial.add(n)”执行递归操作,然后执行“ partial.remove(partial.size -1)”。我重新运行您的代码以确保工作正常。
此解决方案不适用于所有情况。考虑
[1, 2, 0, 6, -3, 3], 3
-仅[1,2], [0,3], [3]
在缺少诸如[6, -3, 3]
它也没有为每个组合的工作,例如
[1, 2, 5], 5
仅输出[5]
的时候[1, 1, 1, 1, 1]
,[2, 2, 1]
并[2, 1, 1, 1]
有解决方案。@cbrad那是因为
i+1
inremaining = numbers[i+1:]
。看来该算法不允许重复。@cbrad要获得包括重复项在内的解决方案,请
[1, 1, 3]
查看stackoverflow.com/a/34971783/3684296(Python)