给定一个包含n个元素的数组(例如[1,2])和一个数字k(例如6),找出产生总和等于k的所有可能方法。
对于给定的示例,答案是4,因为:
1. 1 + 1 + 1 + 1 + 1 + 1 = 6 2. 1 + 1 + 1 + 1 + 2 = 6 3. 1 + 1 + 2 + 2 = 6 4. 2 + 2 + 2 = 6
我能想到的算法是暴力解法,我们模拟所有可能的情况,并在从给定状态无法达到结果时停止。
对于给定的示例,答案是4,因为:
1. 1 + 1 + 1 + 1 + 1 + 1 = 6 2. 1 + 1 + 1 + 1 + 2 = 6 3. 1 + 1 + 2 + 2 = 6 4. 2 + 2 + 2 = 6
1 1 1 1 1 1
1 1 1 1 2
1 1 2 2
2 2 2
我能想到的算法是暴力解法,我们模拟所有可能的情况,并在从给定状态无法达到结果时停止。
arr[] = [1,2]
k = 6
globalCount =0;
function findSum(arr,k)
{
if(k ==0)
globalCount++
return
else if(k<0)
return
for each i in arr{
arr.erase(i)
tmp = k
findSum(arr,tmp)
while(k>=0){
findSum(arr,tmp -= i)
}
}
我不确定我的解决方案是否是最有效的。请评论/纠正或指出更好的解决方案。
编辑:如果有人能给出我的代码的运行时复杂度和他们的解决方案代码,我将非常感激。:) 我认为我的代码复杂度为Big-O(n ^ w),其中w = k / avg(arr [0]..arr [n-1])