H******7
发帖数: 1728 | 1 You are given an array which consist of number between 0 to 5 digit range.
Write a function which will return
true or false, if array can be divided into 2 half such a that sum of the
two half would be equal | s*****y
发帖数: 897 | 2 create too variable sum1 and sum2, both into to 0.
whenever we get a data from the array, we compare sum1 with sum2. Add the da
ta to the smaller one.
Finally, if sum1 = sum2, we get it.
O(N)
【在 H******7 的大作中提到】
: You are given an array which consist of number between 0 to 5 digit range.
: Write a function which will return
: true or false, if array can be divided into 2 half such a that sum of the
: two half would be equal
| r********r
发帖数: 2912 | 3 if the array is {1,2,3,4,5,9}, 1+2+9=3+4+5
But your approach may return false
da
【在 s*****y 的大作中提到】
: create too variable sum1 and sum2, both into to 0.
: whenever we get a data from the array, we compare sum1 with sum2. Add the da
: ta to the smaller one.
: Finally, if sum1 = sum2, we get it.
: O(N)
| H******7
发帖数: 1728 | 4 need more. any thoughts? | l******c
发帖数: 2555 | 5 1, 2, 2, 2, 5
not right
da
【在 s*****y 的大作中提到】
: create too variable sum1 and sum2, both into to 0.
: whenever we get a data from the array, we compare sum1 with sum2. Add the da
: ta to the smaller one.
: Finally, if sum1 = sum2, we get it.
: O(N)
| s*****y
发帖数: 897 | 6 right. That does not work.
【在 l******c 的大作中提到】
: 1, 2, 2, 2, 5
: not right
:
: da
| l*********r
发帖数: 674 | 7 如果所有数的和S，那不就是找个subset sum = S/2，不是NP么？ | l******c
发帖数: 2555 | 8 if the number is random, np or dp problem, can be searched from google
but it is 0, 1, 2, 3, 4, 5
5 = 1 + 4 or 2 +3, so, find one 5, cross out another 5 or one 2 and one 3
or ...
【在 H******7 的大作中提到】
: need more. any thoughts?
| l*********r
发帖数: 674 | 9 0 to 5 digit是5位数还是0-5阿？
anyway，你这个也有问题，比如说给你：
1 2 2 5 1 3 4
你第一步cross out 5 and 1, 4, left is 1 2 2 3
第二步cross out 1 2 and 3， left is 2， 无解。
事实上1 2 2 1 3 和 4 5 是一组解。但是你这做法第一步就把4和5分开了。
所以排列组合还是太多种了。
【在 l******c 的大作中提到】
: if the number is random, np or dp problem, can be searched from google
: but it is 0, 1, 2, 3, 4, 5
: 5 = 1 + 4 or 2 +3, so, find one 5, cross out another 5 or one 2 and one 3
: or ...
| m****v
发帖数: 84 | | s********y
发帖数: 58 | | s*****y
发帖数: 897 | 12 how to use DP to resolve it?
【在 s********y 的大作中提到】
: 经典DP阿
|
|
