Question #219750

Abhay is playing a shooting game. There are n balloon arranged in a row. Each balloon has a number written on it and Abhay can burst balloons from beginning or end. Abhay is really fond of number k and wants to make the sum of all the balloons remaining equal to k. For busting 1 balloon 1 unit of energy is spent by Abhay

Expert's answer

```
import java.util.Arrays;
import java.util.Scanner;
public class ShootingGame {
static int[] numbersCombinations = new int[100];
static int index = 0;
static int possibleCounter = 0;// count of all possible ways
public static void findSumAllBalloons(int[] arr, int start, int length, int sum) {
if (sum == 0) {
possibleCounter++;
} else {
for (int i = start; i < length; i++) {
numbersCombinations[index++] = arr[i];
findSumAllBalloons(arr, i + 1, length - 1, sum - arr[i]);
}
}
index--;
}
/**
* Main method
*
* @param args
*/
public static void main(String[] args) {
Scanner input = new Scanner(System.in); // The first line contains 2 integers
int N = input.nextInt(); // N denoting the number of balloons and
int K = input.nextInt(); // K the sum he want to make.
int balloonNumbers[] = new int[N];
// The next line contains N space separated integers denoting the number written
// on each balloon.
for (int i = 0; i < N; i++) {
balloonNumbers[i] = input.nextInt();
}
Arrays.sort(balloonNumbers);
findSumAllBalloons(balloonNumbers, 0, balloonNumbers.length, K);
System.out.println(possibleCounter+" 1");
input.close();
}
}
```

## Comments

## Leave a comment