/**
   * Method to find a subset of an array of integers summing to k, assuming:
   * - the array a is sorted in nondecreasing order,
   * - we have already considered the elements up to index i, 
   * - the ones we have chosen add up to sum,
   * - the set that are left sum to reamin.
   * The function returns "true" and prints the subset if it is found.
   * Should be first called as findSubset(a,k,-1,0,t), where t is total.
   */
  public static boolean findSubset(int[] a, int k, int i, int sum, int remain) {
    /* Test conditions for expanding this configuration */
    if (i+1 >= a.length) return false;   // safety check that integers remain
    if (sum + remain < k) return false;	// we're undershooting k
    int next = a[i+1];                    // the next candidate integer
    if (sum + next > k) return false;   // we're overshooting k
    if (sum + next == k) {              // we've found a solution!
      System.out.print(k + "=" + next);  // begin printing solution
      return true;
      }
    if (findSubset(a, k, i+1, sum+next, remain-next)) {
      System.out.print("+" + next);      // solution includes a[i+1]
      return true;
      }
    else    // backtracking - solution doesn't include a[i+1]
      return findSubset(a, k, i+1, sum, remain);
  }