target_sum_set_soln_1_java

import java.util.Scanner;
import java.util.Arrays;
import java.util.ArrayList;

public class SumSet {
    static void sum_up_recursive(int start, ArrayList<Integer> partial) {

       //System.out.println(Arrays.toString(partial.toArray())); //print this to understand
       int sum = 0;

       for (int x: partial) sum += x;

       //base conditions this will stop recursion
        if (sum == target && partial.size() == k){
            ansCnt += 1;
            System.out.println("ans "+ansCnt+": "+Arrays.toString(partial.toArray()));
            return;
        }

        if (sum > target || partial.size() > k){
            return;
        }

        for(int i=start; i<numbers.length; i++) {
            start = i+1;
            ArrayList<Integer> partial_rec = new ArrayList<Integer>(partial);
            partial_rec.add(numbers[i]);
            sum_up_recursive(start, partial_rec);
       }
    }


    static int[] numbers;
    static int target;
    static int k;
    static int start =0;
    static int ansCnt = 0;


    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);

        int n = scan.nextInt();
        target = scan.nextInt();
        k = scan.nextInt();

        numbers = new int[n];
        for(int i =0; i < n; i++){
            numbers[i] = scan.nextInt();
        }

        Arrays.sort(numbers); // required

        // optional
        int idx = Arrays.binarySearch(numbers,0,numbers.length,target);


        if(k == 1){
            if(idx > -1){
                System.out.print("ans 1: "+numbers[idx]);
            }
            else{
                System.out.print("no solution");
            }
        }
        else{
            sum_up_recursive(start, new ArrayList<Integer>());
            if(ansCnt == 0) System.out.println("no solution");
        }


    }
}

// reference https://stackoverflow.com/questions/4632322/finding-all-possible-combinations-of-numbers-to-reach-a-given-sum

/*
input:
6 <--n
10 <-- target
4 <--k
3 7 1 9 -1 5
-1 -2 9 3 10 5

output:
ans 1: [-1, 1, 3, 7]


*/

/*

don't slice array based on target
edge case:
6
6
3
-1 -2 9 3 10 5 // due to negative number even number 9 can be used to generate set [-2, -1, 9]
ans 1: [-2, -1, 9]
ans 2: [-2, 3, 5]
*/