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

namespace _030_Backtracking
{
    class Backtracking
    {
        protected int[] st; // stiva solutie
        protected int top; // varful stivei
        protected int dimmax; //dimensiunea maxima a stivei
        protected int vmin, vmax; //valoarea minima si maxima care se pot pune pe un nivel de stiva
        public Backtracking(int _top, int _dimmax, int _vmin, int _vmax)
        {
            top = _top;
            dimmax = _dimmax;
            vmin = _vmin;
            vmax = _vmax;
        }
        public virtual void Afisare()
        {
            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;
        }
    }
    //Se dau S,n. Sa se scrie S ca suma de numere naturale
    //nenule distincte
    // S = 12, n = 3 : (1,2,9) (1,3,8) ... (3,4,5)
    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()
        {
            int s = 0;
            if (st[top-1] >= st[top]) return false;
            for (int i = 0; i <= top; i++)
                s += st[i];
            if (s > S) return false;
            if (top == dimmax && s != S)
                return false;
            return true;
        }
    }
}