If you split it into two groups A and B
Then you can calculate the change in sums by swapping any pair of numbers from 1 to the other set (or just by moving a small number from 1 set to the other). If you find the swap that puts it closest to Y = Z then you'd converge to an almost-solution pretty quickly.
When there are no swaps that put it closer to equal, then you'd extend the number of swaps up to the number of elements in each set 1 at a time looking for a closer solution. (eg. 1 from set A, 2 from set B, then 2 from set A, 1 from set B)
If you get up to swapping 1/2 the elements from each set you know it's not possible, similar reasoning to yours (swapping more than half of each set is the same as swapping the other smaller half)
I think this is better than your way since instead of going to permutations on 1/2 the numbers in X, you go to permutations on two halves. Which if I remember right permutations are factorial growth so cutting the limit in half and then multiplying the product is good. (8!8! < 16!)
Changing your set so it would theoretically have a split
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 36
Split halfway (faster would be to add items to set A until it's >= 1/2 the total)
2 3 5 7 11 13 (41) | 17 19 23 29 31 36 (155)
Moving 36 from set 2 to set 1 changes it toward the middle [98] the best
2 3 5 7 11 13 36 (77) | 17 19 23 29 31 (119)
Moving 19 from set 2 to set 1 changes it toward the middle the best
2 3 5 7 11 13 19 36 (96) | 17 23 29 31 (100)
Moving 2 from set 1 to set 2 makes them match
3 5 7 11 13 19 36 (98) | 2 17 23 29 31 (98)
This should improve find times on sets with a solution, and not end up any worse on sets without one.. dunno how much that helps.
Artificial example that won't solve just by moving single numbers
80 17 (97) | 83 20 (103)
No single movement gets closer to 100...
Swapping 17 & 20 though...
80 20 (100) | 83 17 (100)
I guess this is variation on the backpack problem.. how do you put as many items in the backpack as possible if they have fixed size {S}
Then you can calculate the change in sums by swapping any pair of numbers from 1 to the other set (or just by moving a small number from 1 set to the other). If you find the swap that puts it closest to Y = Z then you'd converge to an almost-solution pretty quickly.
When there are no swaps that put it closer to equal, then you'd extend the number of swaps up to the number of elements in each set 1 at a time looking for a closer solution. (eg. 1 from set A, 2 from set B, then 2 from set A, 1 from set B)
If you get up to swapping 1/2 the elements from each set you know it's not possible, similar reasoning to yours (swapping more than half of each set is the same as swapping the other smaller half)
I think this is better than your way since instead of going to permutations on 1/2 the numbers in X, you go to permutations on two halves. Which if I remember right permutations are factorial growth so cutting the limit in half and then multiplying the product is good. (8!8! < 16!)
Changing your set so it would theoretically have a split
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 36
Split halfway (faster would be to add items to set A until it's >= 1/2 the total)
2 3 5 7 11 13 (41) | 17 19 23 29 31 36 (155)
Moving 36 from set 2 to set 1 changes it toward the middle [98] the best
2 3 5 7 11 13 36 (77) | 17 19 23 29 31 (119)
Moving 19 from set 2 to set 1 changes it toward the middle the best
2 3 5 7 11 13 19 36 (96) | 17 23 29 31 (100)
Moving 2 from set 1 to set 2 makes them match
3 5 7 11 13 19 36 (98) | 2 17 23 29 31 (98)
This should improve find times on sets with a solution, and not end up any worse on sets without one.. dunno how much that helps.
Artificial example that won't solve just by moving single numbers
80 17 (97) | 83 20 (103)
No single movement gets closer to 100...
Swapping 17 & 20 though...
80 20 (100) | 83 17 (100)
I guess this is variation on the backpack problem.. how do you put as many items in the backpack as possible if they have fixed size {S}