(defun ten-to-bin (x len)
  "Создает вектор бит фиксированной длины (аналог маски)."
  (let ((mask (make-array len :element-type 'bit :initial-element 0)))
    (loop for i from (1- len) downto 0
          while (> x 0)
          do (multiple-value-bind (quotient remainder) (truncate x 2)
               (setf (aref mask i) remainder)
               (setf x quotient)))
    mask))

(defun calculate-sum (numbers-vec mask-vec)
  "Считает сумму элементов вектора по маске. Использует across для векторов."
  (loop for num across numbers-vec
        for flag across mask-vec
        when (= flag 1)
        sum num))

(defun find-sum (target numbers-vec)
  (declare (optimize (speed 3) (safety 0) (debug 0))
           (type (simple-array fixnum (*)) numbers-vec)
           (type fixnum target))
  (let* ((len (length numbers-vec))
         (total (1- (ash 1 len)))
         (current-sum 0)
         ;; Массив для отслеживания текущего состояния (биты)
         (bits (make-array len :element-type 'bit :initial-element 0)))
    (declare (type fixnum current-sum))
    
    (format t "Combinations: ~D~%" total)
    
    ;; Итерация по Коду Грея
    (loop for i fixnum from 1 to total do
      (let* ((gray-diff (logand i (- i))) ; Находим индекс изменяемого бита
             (bit-idx (1- (integer-length gray-diff)))
             (num (aref numbers-vec bit-idx)))
        (declare (type fixnum bit-idx num))
        
        ;; Если бит был 0, прибавляем число, если 1 — вычитаем
        (if (zerop (aref bits bit-idx))
            (progn 
              (incf current-sum num)
              (setf (aref bits bit-idx) 1))
            (progn
              (decf current-sum num)
              (setf (aref bits bit-idx) 0)))
        
        ;; Проверка цели
        (when (= current-sum target)
          (format t "Found: ~A~%" bits)
          (return-from find-sum bits))))
    nil))

(defun main (args)
  (let ((len (length args)))
    (if (or (< len 5) (> len 30))
        (progn
          (format t "ER: input parameters~%")
          (uiop:quit 1))
        (let* ((target (parse-integer (first args)))
               (numbers-vec (coerce (mapcar #'parse-integer (rest args)) 'vector)))
          (find-sum target numbers-vec)))))