jacksu said:
Say i have int array, want to know all the sum combination, ignore
orders.
say [1, 2, 3]
have
[1, 2 ,3]
[3, 3]
[1, 5]
[4, 2]
[6]
How to write efficient java program to do so? The array size from 2 to
1000.
Assuming I understand your needs well, the expected result may consist of:
i) each k-combination without repetitions of n-elements input array;
where k changes from 0 to n-2 (inclusive), with a single additional
element which is a sum of n-k elements not contained in combination; and
ii) an input array itself.
See results (r) of applying this algorithm to your example array:
n: 3
// applying i):
k: 0
r: [] + (6) = [6]
k: 1
r: [1] + (5) = [1, 5]
r: [2] + (4) = [2, 4]
r: [3] + (3) = [3, 3]
// applying ii):
r: [1, 2, 3]
Notice that using above algorithm you will need iterative combination
series generator. This is because in expected case of 1000 elements
input array the result will consist of
10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668068376
distinct arrays, which will probably not fit into your machine memory.
An example of iterative combinations generator you can find here:
http://mindprod.com/jgloss/combination.html
Regards,
piotr