PHP-请教一个多对一的算法

PHP-请教一个多对一的算法

晚风撩人 发布于 2016-12-20 字数 425 浏览 1098 回复 1

function isMatch($array,$target){
}
match的规则是,先在$array里面找,有没有一个元素$array[i]==$target,如果有则返回true,如果没有,继续找有没有任意两个元素相加==$target,即$array[i]+$array[j]==$target;如果还是没有继续找有没有任意三个元素相加==$target,以此类推,只到count($array)个相加能不能==$target为止,最终如果还是没找到,则返回false.
非常感谢
什么语言都可以,不一定非是php呀,我只想看看算法思路

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(1

瑾兮 2017-10-26 1 楼

下面是java实现算法:

public class Test {

private static int count = 0;

/**
* @param args
*/
public static void main(String[] args) {
int[] a = { 2,5,6,9,11,13,20,29,30,31,40 };
System.out.print(isMatch(a, 30));
}

public static boolean isMatch(int[] array, int target) {
Arrays.sort(array);
LinkedList<Integer> stack = new LinkedList<Integer>();
findMatch(array, 0, target, stack);
return count > 0;
}

public static void findMatch(int[] array, int start, int target,
LinkedList<Integer> stack) {
for (int i = start; i < array.length; i++) {
if (array[i] == target) {
stack.push(array[i]);
printStack(stack);
count++;
stack.pop();
} else if (array[i] < target) {
stack.push(array[i]);
findMatch(array, i + 1, target - array[i], stack);
stack.pop();
} else {
return;
}
}

}

public static void printStack(List<Integer> stack) {
System.out.print("find a solution: ");
for (int i : stack) {
System.out.print(i + " ");
}
System.out.println();
}

}