プロジェクトオイラー問105 - sinapusu2002 @ ウィキ

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20105
Problem 105 「特殊和集合:検査」 †
与えられた数字列が特殊和集合を満たしいるかチェックする問題。

解法
問題を考えます。
例えば３個と４個を比べる場合。
すべての3個と４個で条件を満たすなら２個と４個、１個と４個を検討する必要はありません。
つまりｎ個の合計より一つ少ない合計と比較すればよいと分かります。

また問題を言い換えると例えば３個と４個なら。
３個の中で最も大きな合計と４個の中で最も小さい合計を比べて４個のほうが大きければ問題の条件を満たすとなります。

ところで全部を比べると一番確実に条件を満たさない可能性があるのは
３個と４個に例をとれば３個の最大値と４個の最小値を比べることです。
３個の最大値とは数字列の中の一番大きな数字３つを足すことであり。
４個の最小値とは数字列を小さい数字から４つ足す場合です。
つまりはｎ個とｎ-1個の比較は手計算でも一瞬です。

これで答えは出ると考えられますが、３個と３個が同じ和にならないようなケースを考えるためにどうしてもｎ個の場合での合計すべては計算する必要がありますがこれはそんなに組み合わせは多くありません。

これらを考慮すれば計算はかなり早くなります。
計算時間　０．０９４秒でした。

sum([],Sum,Sum):-!.
sum([X|Xs],Sum,Result):-
	Sum1 is Sum+X,
	sum(Xs,Sum1,Result).

search(_,0,_,Sum,Sum):-!.
search([X|Xs],N,N,Sum,Result):-
	!,
	Sum1 is Sum+X,
	N1 is N-1,
	search(Xs,N1,N1,Sum1,Result).
search([X|Xs],N,Rest,Sum,Result):-
	N1 is N-1,
	Rest1 is Rest-1,
	Sum1 is Sum+X,
	search(Xs,N1,Rest1,Sum1,Result).
search([_|Xs],N,Rest,Sum,Result):-
	Rest1 is Rest-1,
	search(Xs,N,Rest1,Sum,Result).


check([X],1):-
	length(X,Len),
	sort(X,X1),
	length(X1,Len),
	!.

check([_],0):-!.
check([X1,X2|Rest],Result):-
	length(X1,Len),
	sort(X1,X11),
	length(X11,Len),
	reverse(X11,[Max|_]),
	sort(X2,[Min|_]),
	Max<Min,
	!,
	check([X2|Rest],Result).
check(_,0):-!.

create2(Es,Es1):-
 	length(Es,Len),
	between(1,Len,N),
	N*2-1=<Len,
	findall(E,search(Es,N,Len,0,E),Es1).
create(Es,Result):-
	findall(E,create2(Es,E),Es1),
	check(Es1,Re),
	sum(Es,0,Sum),
	Result is Re*Sum.
 


main:-
	see('pe105.txt'),
 	read(R),
	seen,
	findall(E2,(member(E1,R),create(E1,E2)),Es),
	sum(Es,0,Ans),
	write(Ans).