java对于这种递归算法,什么是好的迭代解决方案?
问题:给定数组和目标编号,打印可写入数组中元素的唯一组合的方式数
示例:
array = {1,2,3} target = 4
4 = {2,2}, {3,1}, {1,1,1,1} //numbers can be repeatedly selected from the array.
Ans: 3 ways
递归解决方案
F(4) = F(4-1) + F(4-2) + F(4-3)
F(4) = F(3) + F(2) + F(1)
...
Total sum是每次递归调用函数并减去数组值作为参数的总和
从概念上讲,重复可以表示为(具有讽刺意味的是作为迭代):
for(int i=0; i<array.length; i++)
sum+=F(target - array[i]);
基本情况:
F(0) = 1 //Implies sums to target
F(<0) = 0 //Implies cannot sum to target
然而,即使对于上面的一个小例子,它也会导致StackOverflower错误。如何最好地迭代以下解决方案:
代码
public class CombinationSum {
private int[] array;
private int target;
public CombinationSum(int[] array, int target)
{
this.array = array;
this.target = target;
}
public int recurSum(int val)
{
int sum = 0;
if(val < 0 )
return 0;
else if(val == 0)
return 1;
else
{
for(int i = 0; i<array.length; i++)
{
sum+= recurSum(target-array[i]); //heavy recursion here?
}
return sum;
}
}
public static void main(String[] args)
{
int target = 4;
int[] array = {1,2,3};
CombinationSum cs = new CombinationSum(array, target);
System.out.println("Number of possible combinations: "+cs.recurSum(target));
}
}
# 1 楼答案
下面是Python中的一个解决方案
# 2 楼答案
伪代码