//*** CODE ***
/*
Online Java - IDE, Code Editor, Compiler
Online Java is a quick and easy tool that helps you to build, compile, test your programs
online.
*/
// This has been created to ensure I can utilize any random functions more efficiently.
// It is a creation of the combinations (with replacement) calculator.
// It has used techniques I learnt including recursion and also memoization to speed up execution.
// I will incorporate this into Java applications I created previously..
//TEST CASES
// All done on My Approach

//NOTE THE CODE IS MASSIVELY COMMENTED OUT AND PRESERVED CRITICAL COMMENTS ON THE SCREEN....

import java.math.*;
import java.util.*;

class Staircase
{
    static int subsetEntry=0;
    boolean executeOnce=false;
    static int k = 24;
    int[] S;
    int p;
    int total;
    int cycles=0;
    int maxRValue;
    static int totalcycles=0;
    static int difference = 0;
    static int i=0;
    
    static List <String> backupValuesSet = new ArrayList<>();
    
    Set<String> st;
    Random rand = new Random();
    static String[] valuesSet;
    String []backupValuesSetBeforeModification;
    
    public Staircase(long combinations, int[] X, int r, Set<String> st, int maxRValue)
    {
        this.S=S;
        this.st=st;
        this.maxRValue=maxRValue;
        System.out.println("Combinations: " + combinations);
        StringJoiner sj = new StringJoiner(",");
        StringJoiner sj1 = new StringJoiner(",");
        
        int currentSetSize=0;
        int newSetSize;
        int q;
        int steps;
        boolean allSameDigit=true;
        
        String subsetIntToString="";
        int countSameNumber=0;
        int pos=0;  
        int previousI=0;
        
        int n=0;
        
        for (int i: X)
        {
            subsetIntToString =  Integer.toString(i);
            
            if (pos>0)
            {
                if (previousI!=i )
                {
                    allSameDigit=false;
                }
            }
            previousI=i;
            pos++;
        }
        
        do
        {
            sj1.add(subsetIntToString);
            countSameNumber++;
            
        }while(countSameNumber<(maxRValue/X[0]));
        
        if (allSameDigit)
        {
            System.out.println("\nk is equal to: " + k);
            System.out.println("This is the solution: " +  sj1.toString());
            
            System.exit(0);
        }
        System.out.println("*************INITIAL VALUE OF  CYCLES: " + cycles);
        
        do
        {
            for (q=0; q<r;q++)
            {
                p= rand.nextInt(X.length);
                steps = X[p];
                sj.add(Integer.toString(X[p]));
                currentSetSize=st.size();
                total=total+steps;
                
                if (total==k)
                {
                    st.add(sj.toString());
                }
                
                if (q==r-1)
                {
                    sj = new StringJoiner(",");
                    total=0;
                }
            }
            
            if (total>k)
            {
                total=0;
                sj = new StringJoiner(",");
            }
            
            newSetSize = st.size();
            
            if (newSetSize>currentSetSize)
            {
                
            }
            cycles++;
            totalcycles++;
        
        }while (cycles<combinations*40);
        
        valuesSet = st.toArray(new String[st.size()]);
        backupValuesSetBeforeModification = st.toArray(new String[st.size()]);
        System.out.println("******************Contents of the backup set");
        
        for (String g: backupValuesSet)
        {
            System.out.println(g);
        }
        
        System.out.println("******************Contents of the valuesSet");
        
        for (String g: valuesSet)
        {
            System.out.println(g);
        }
        
        for (String m: backupValuesSet)
        {
            n=0;
            do
            {
                if (m==valuesSet[n])
                {
                    System.out.println("Match found in backupValuesSet: " + m);
                    System.out.println("Match found in valuesSet: " + valuesSet[n]);
                    
                    valuesSet[n]="ALREADY PROCESSED";
                    System.out.println("valuesSet[n]" + " set to " + valuesSet[n]+"\n");
                }
                n++;
                
            }while (n<valuesSet.length);
        }
        
        System.out.println("*************NEW VALUE CYCLES: " + cycles);
        System.out.println("*************RUNNING TOTAL CYCLES: " + totalcycles);
        
        System.out.println("***PROCESSING SET AT INDEX: " + (difference));
        System.out.println("**ENDING AT INDEX:***** " + st.size());
        
        backupValuesSet= new ArrayList<>(Arrays.asList(backupValuesSetBeforeModification));
        
        for (int entry=0; entry<valuesSet.length; entry++)
        {
            if (valuesSet[entry]!="ALREADY PROCESSED")
            {
                subsetEntry++;
                
            System.out.println(valuesSet[entry] + "    Subset: " + subsetEntry  + "  at cycle number: " + totalcycles);
            }
        }
        difference = newSetSize;
        
        }
}
public class Combination
{
    static Staircase sc;
    
    public static void main(String[] args)
{
    System.out.println("Welcome to Online IDE!! Happy Coding :)");
    int originalNumber=0;
    int n=originalNumber;
    int r;
    
    Set <String> s = new HashSet<>();
    
    //int [] X = new int []{1,2,3,4}; //user defined
    //int [] X = new int []{2,1,4}; //user defined
    //int [] X = new int []{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
    //int [] X = new int []{7,4,9};
    int [] X = new int []{12,1,61,5,9,2};
    //int [] X = new int []{1,2,1,2,1,1}; //user defined
    
    int counter=0;
    int minimum;
    int maxRValue;
    
    
    //need to understand that r can be greater than n in replacement.......
    //r is taken from n objects
    // in this example, r can get larger....
    
    Map <Integer, Long> m;
    n=X.length;
    originalNumber=n;
    
    m= new HashMap<>();
    minimum=X[0];

    for (int i=0; i<X.length;i++)
    {
        if (X[i]<minimum && X[i]!=0)
        {
            minimum=X[i];
        }
    }
    maxRValue=(Staircase.k)/minimum;
    
    if (maxRValue>=64)
    {
        System.out.println("Value of r=" + maxRValue + " is too high computationally. It will be reduced to: " + (maxRValue-1));
    }
    
    for (r=0; r<=maxRValue+1; r++)
    {
        System.out.println("\n***COMBINATIONS*** (WITH REPLACEMENT)");
        
        System.out.println("C^R(n + r) = " + "(n+r-1)! / r!(n-1)!");
        
        System.out.println("C^R(" + n+","+r+") = " + (n+r-1)+ "!" + " / " + r+"!"+"("+(n-1)+")!");
        
        sc = new Staircase (Combinations (n,r,originalNumber, m), X, r,s, maxRValue);
        
    }
    System.out.println("\n\n*************ALL UNIQUE ENTRIES*************");

    Iterator iterator = sc.st.iterator();
    
    while (iterator.hasNext())
    {
        System.out.println(iterator.next());
    
        counter++;
    }
    
    System.out.println(counter + " unique combinations");
    System.out.println(FoundSubset());
    
}

public static String FoundSubset()
{
    try
    {
    if (sc.valuesSet[0].isEmpty())
    {
        return null;
    }
    
    }
    catch (ArrayIndexOutOfBoundsException e)
    {
        return null;
    }
    return "";
}

public static long Combinations (int n, int r, int originalNumber, Map factorialResults)
{
    long result=0;
    int denominator1;
    int denominator2;
    int Numerator=n+r-1;
    int zero=0;
    long zeroFactorial = 1;
    
    if (originalNumber==0 && r==0)
    {
        System.out.println("n and r can not both be equal to zero");
        
        return 0;
    }

    if (originalNumber==0 && originalNumber+r-1<r)
    {
        System.out.println("n+r-1 must be > or = to r");
        return 0;
    }
    
    if (Numerator>=1)
    {
        result = ((n+r-1)* (Combinations (n-1, r,originalNumber, factorialResults)));
        factorialResults.put(Numerator,result);
        
        if (n==originalNumber)
        {
            denominator1 = r;
            denominator2 = originalNumber-1;
            factorialResults.put(zero,zeroFactorial); //0! is equal to 1
            
            if (factorialResults.containsKey(denominator1) && factorialResults.containsKey(denominator2))
            {
                long returnValue = result / ((long)factorialResults.get(denominator1) *(long)factorialResults.get(denominator2));
                return returnValue;
            }
            
        }
        return result;
    }
    return 1; // it will reach here only when condition not met (Numerator>=1)
    }
}