Solução escrita por Enzo Dantas
Conhecimento prévio necessário:
Primeiramente vamos simplificar o problema: temos o conjunto dos números de 1 até N e queremos dividí-lo em dois conjuntos de mesma soma. Se a soma total é ímpar, então é impossível.
Primeira ideia:
A primeira ideia para resolver o problema se baseia no funcionamento da soma de gauss. Vamos dividir a solução em dois casos, N ímpar e N par.
N par: para N=8, por exemplo, sabe-se que 1+8 = 2+7 = 3+6 = 4+5. Sabe-se também que, se N é par e a soma é divisível por 2, então há um número par desses pares cuja soma é igual a 1+N, pois 1+N é ímpar nesse caso. Logo, temos 
pares e podemos colocar os 
pares no primeiro conjunto e os restantes no segundo conjunto.
N ímpar: para N=7, por exemplo, não podemos dividir exatamente como fizemos para o caso de N par, mas podemos fazer a seguinte divisão, que é semelhante: 1+6 = 2+5 = 3+4 = 7. Analogamente, sabemos que existe um número ímpar de pares de soma 1+(N-1) e um único número isolado N. Logo, é possível colocar os 
primeiros pares no primeiro conjunto e o restante dos pares mais o número N no segundo conjunto.
Recomendamos que você tente implementar o problema antes de ver o código. Veja a implementação nesse link.
Segunda ideia:
Uma segunda ideia, que é bem mais simples de implementar, se baseia na ideia de binary jumping e na representação de um número em binário. Se queremos representar 37 em binário, por exemplo, pegamos a maior potência de 2 menor ou igual a 37, adicionamos ela na representação, subtraímos essa potência de 37 e repetimos o processo. Demonstração: 37-32 = 5. 5-4 = 1. 1-1 = 0. 37 = 100101.
Usaremos essa ideia para criar um conjunto de soma = soma_total/2. Para N=12, por exemplo, queremos chegar no valor 
= 39. Temos o conjunto dos números de 1 até 12, e vamos continuamente subtrair o maior número não usado e adicioná-lo a resposta. Demonstração: 39-12 = 27. 27-11 = 16. 16-10 = 6. 6-6 = 0. Conjunto 1 = {12, 11, 10, 6}, conjunto 2 = {9, 8, 7, 5, 4, 3, 2, 1}.
Prova que o algoritmo funciona: enquanto a soma restante for maior que o maior número, subtraímos o maior número, então todos os números menores que ele ainda estão disponíveis. Quando a soma restante eventualmente virar X tal que X é menor ou igual ao maior número, com certeza ainda não teremos usado esse número, então podemos adicionar X no conjunto, chegando a soma certa.
Recomendamos que você tente implementar o problema antes de ver o código. Veja a implementação nesse link.