// optional recursion solution class

public class ListRecursion {
  public static void main(String[] args) {
    char[] c3 = {'a', 'b', 'c'};
    char[] c4 = {'a', 'b', 'c', 'd'};
    int[] i3 = {2, 3, 5};
    int[] i6 = {1, 2, 3, 4, 5, 6};
    System.out.println("- - - - - - - - - - - - - - - - -");
    System.out.print("set: ");
    System.out.println(c3);
    System.out.println("All subsets: ");
    subsets(c3);
    System.out.println("All subsets with 2 elements: ");
    subsetsN(c3, 2);
    System.out.println("All permutatons: ");
    permute(c3);
    System.out.println("- - - - - - - - - - - - - - - - -");
    System.out.print("set: ");
    System.out.println(c4);
    System.out.println("All subsets: ");
    subsets(c4);
    System.out.println("All subsets with 1 element: ");
    subsetsN(c4, 1);
    System.out.println("All subsets with 2 element: ");
    subsetsN(c4, 2);
    System.out.println("All permutatons: ");
    permute(c4);
    System.out.println("- - - - - - - - - - - - - - - - -");
    System.out.print("Consider numbers: ");
    for (int j = 0; j < i3.length; j++)
      System.out.print(" " + i3[j]);
    System.out.println();
    System.out.println(countSums(i3, 5)  + " sums adding to 5");
    System.out.println(countSums(i3, 4)  + " sums adding to 4");
    System.out.println("- - - - - - - - - - - - - - - - -");
    System.out.print("Consider numbers: ");
    for (int j = 0; j < i6.length; j++)
      System.out.print(" " + i6[j]);
    System.out.println();
    System.out.println(countSums(i6, 6)  + " sums adding to 6");
  } // end of main

// - - - - - start of method solutions - - - - - - - - -

  // Print all subsets of e, one per line, 
  //    assuming all elements of e are distinct.
  public static void subsets(char[] e) {
    // Implement as multistep process:  include or do not include next char.
 
    subsetsRest(e, new boolean[e.length], 0);
  }

   private static void subsetsRest(char[] e, boolean[] isIn, int iStart) {
    /*
    e is the array of possible characters.
    e[j] is in the set if isIn[j] is true, for each j < iStart.
    isIn[j] is false for each j >= iStart.
    isIn ends in the same state it starts the method.
    The method provides all choices of true and false values for every
    index >= iStart, and prints the result if iStart == e.length.
    */

    if (iStart == e.length) {
      for (int j = 0; j < e.length; j++)
        if(isIn[j]) System.out.print(e[j]);
      System.out.println();
    }
    else {
      isIn[iStart] = true;
      subsetsRest(e, isIn, iStart+1);  // do include e[iStart]
      isIn[iStart] = false; // placing isIn back in its original state
      subsetsRest(e, isIn, iStart+1);  // not include e[iStart]
    }
  }

  // Print all subsets of e with n elements, one subset per line,
  //    assuming all elements of e are distinct, and 0 <= n <= e.length.
  // (This can be derived from previous code, assembling all subsets,
  //   but try to do it more directly.)
  public static void subsetsN(char[] e, int n) {
    // Implement as multistep process:  include or do not include next char.
 
    subsetsNRest(e, new char[n], 0, 0);
  }

  private static void subsetsNRest(char[] e, char[] sub, int eStart, int subStart) {
    /*
    e is the array of possible characters.
    If eStart == e.length, and subStart < sub.length, return doing nothing.
    If subStart == sub.length, print sub.
    Letters sub[j] are chosen already if j < subStart.
    Fill remaining places in sub with some elements e[k], k >= eStart.
    Returns with sub[j] unchanged if j < eStart.
    */

    if (subStart == sub.length)
      System.out.println(sub);
    else if (eStart < e.length) {
      sub[subStart] = e[eStart];
      subsetsNRest(e, sub, eStart+1, subStart+1); // do add e[eStart]
      subsetsNRest(e, sub, eStart+1, subStart); // do not add e[eStart]
    }
  }

  // Print out the elements of e in all possible orders,
  //    assuming all elements of e are distinct.
  public static void permute(char[] e) {
    // implement as multistep process:
    //   choose element at index i from elements now at index >= i

    permuteRest(e, 0);
  }

  private static void permuteRest(char[] e, int iStart) {
    /*
    e is a possible permutation.
    Keep e[j] in its position if j < iStart.
    Do all permutations for elements e[j], j >= iStart.
    Return with the order of e elements the same as the beginning.
    */

    if (iStart == e.length)
      System.out.println(e);
    else
      for (int j = iStart; j < e.length; j++) {
        swap(e, iStart, j); // helping method next
        permuteRest(e, iStart+1);
        swap(e, iStart, j); // return to original state
      }
  }

  private static void swap(char[] e, int i, int j) {
    char temp = e[i];
    e[i] = e[j];
    e[j] = temp;
  }

  // Return a count of all the sums of subsets of one or more elements from x 
  //   that add to sum.  Order does not matter.
  // For simplicity you may assume that all the elements of x are distinct.
  // Again this could be done by assembling all subsets, but do it more directly.
  public static int countSums(int[] x, int sum) {  
    // Implement as multistep process:  include next number or not in sum.

    return countSumsRest(x, sum, 0);
  }

  private static int countSumsRest(int[] x, int sumMissing, int iStart) {
    /*
    x is the array of numbers you can add.
    sumMissing is the desired sum from some of the element x[j], j >= iStart.
    */
    
    if (iStart == x.length) return 0;
    int count = 0;
    count += countSumsRest(x, sumMissing, iStart+1);// sums not using x[iStart]
    sumMissing -= x[iStart];                        // do use x[iStart]
    if (sumMissing == 0) count++;                   // sum ending here?
    count += countSumsRest(x, sumMissing, iStart+1);// longer sums using x[iStart]
    return count;
  }
} // end of ListRecursion