/* 

  Subsets 100 puzzle in Picat.

  From rec.puzzle FAQ
  http://brainyplanet.com/index.php/Subsets?PHPSESSID=051ae1e2b6df794a5a08fc7b5ecf8028
  """
  Out of the set of integers 1,...,100 you are given ten different integers. 
  From this set, A, of ten integers you can always find two disjoint non-empty 
  subsets, S & T, such that the sum of elements in S equals the sum of elements 
  in T. Note: S union T need not be all ten elements of A. Prove this.
  """

  This program was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

import cp.

main => go.

go =>
  N = 100,
  M = 10,
  
  subsets_n(N, M, S, T),
  
  println(s=[I : I in 1..N, S[I] == 1]),
  println(t=[I : I in 1..N, T[I] == 1]),  
  nl,
  fail,
  
  nl.

go2 => 
  N = 100,
  M = 10,
  
  Counts = count_all(subsets_n(N, M, _S, _T)),
  println(counts=Counts),
  nl.

subsets_n(N, M, S, T) =>
  S = new_list(N),
  S :: 0..1,

  T = new_list(N),
  T :: 0..1,

  sum(S) #> 0,
  sum(T) #> 0,
  % sum(S) #= sum(T), % experimental

  sum(S) + sum(T) #<= M,

  sum([I*S[I] : I in 1..N]) #= sum([I*T[I] : I in 1..N]),


  Vars = S ++ T,

  solve($[],Vars).