using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _026_Backtracking
{
    class BackTracking
    {
        protected int[] st; // stiva solutiei
        protected int top; // varful stivei
        protected int dimmax; // dimensiunea maxima a stivei
        protected int vmin, vmax; // valorile minima si maxima care se pot
        // pune pe un inel de pe stiva
        public BackTracking(int _top, int _dimmax, int _vmin, int _vmax)
        {
            top = _top;
            dimmax = _dimmax;
            vmin = _vmin;
            vmax = _vmax;
        }
        public virtual void Afisare() // afisare solutie
        {
            int i;
            for (i = 1; i <= top; i++)
                Console.Write(st[i] + " ");
            Console.WriteLine();
        }
        public virtual bool Valid()
        {
            return true;
        }
        public void Back()
        {
            bool cand;
            while (top > 0)
            {
                cand = false;
                while (!cand && st[top] < vmax)
                {
                    st[top]++;
                    cand = Valid();
                }
                if (!cand) top--;
                else if (top == dimmax) Afisare();
                else st[++top] = vmin;
            }
        }
    }

    class Permutari : BackTracking
    {
        public Permutari(int _top, int _dimmax, int _vmin, int _vmax)
            : base(_top, _dimmax, _vmin, _vmax)
        {
            st = new int[dimmax + 1];
        }

        public override bool Valid()
        {
            int i;
            for (i = 1; i < top; i++)
                if (st[i] == st[top]) return false;
            return true;
        }
    }

   class Sume : BackTracking
    {
        protected int S;
        public Sume(int _top, int _dimmax, int _vmin, int _vmax, int _S)
            : base(_top, _dimmax, _vmin, _vmax)
        {
            st = new int[dimmax + 1];
            S = _S;
        }
        public override bool Valid()
        {
            if (st[top - 1] >= st[top]) return false;
            int s = 0;
            for (int i = 1; i <= top; i++)
                s += st[i];
            if (s > S) return false;
            if (top == dimmax && s != S) return false;
            return true;
        }
    }
}