(*Problem:

A list of integers is called zero-sum if the sum of its elements is 0 and balanced if it is the least zero-sum list among its non-empty sublists. Given a list l it is to find the balanced sublists of l.*)

(* sum up a list of integers *)
let sumup l =
  List.fold_left (+)  0 l
;;
(* the sublists of a list are precisely the prefixes of all suffixes *)
let balanced l =
(* check the prefix of each tail *)
let rec balanced_bw l n =
  match l with
  [] -> []
  | h::t ->
    let bsl = balanced_bw t ( n - h ) in
    (* zero-sum and minimality *)
    if ( n = 0 && bsl = [] )
    then [l]
    else bsl
in
(* check all tails of a list *)
let rec balanced_fw l n =
  match l with
  [] -> []
  | h::t -> ( balanced_bw ( List.rev l ) n )@( balanced_fw t ( n - h ) )
in
  balanced_fw l ( sumup l )
;;

(* Test Code *)

let rec print_loint l =
  match l with
  [] -> ()
  | h::t -> Printf.printf "%d " h ; print_loint t
;;

let rec print_lol l =
  match l with
  [] -> ()
  | h::t -> print_loint h ; Printf.printf "\n" ; print_lol t
;;

print_lol ( balanced [1;1;-1;1] );;