Introduction This programming assignment is meant for practicing recursion, and this document will guide you to the final solution.

2 Description of problem Alice and Bob saw an interesting matrix of size n*n online, and they decide to play a game based on this matrix. The game has four rules:

1. They will start from [0,0]

2. They could only move straight up or to the upper right slots.

3. When they are in the top row(i.e. row n-1), the game ends.

4. They will add up the numbers along the way. The one who has the highest score wins the game In the above example, the possible paths for the would be {10, 2, 4, 5}, {10, 3, 6, 9}, {10, 3, 5, 1}... Bob doesnt know what a good strategy would be to win the game, so he asks you to write a program to print all distinct possible sums of the paths he could take from the first row to the top role

Table 1: Example Map

5	1	9	10
4	5	6	0
2	3	0	0
10	0	0	0

Analysis of the problem

Recurrence Relation When you saw this problem, you decided to write a program just to enumerate all possible paths that Bob could travel. Suddenly, you think you could use what you just learned in COMP550 about recurrences to solve this problem.

1. Suppose you are at position[0][0], what would be the next possible moves for you? And could these be generalized to any coordinates[i][j]?(i representing rows and j representing columns)

2. Based on your answer for part 1, what would be the upper bound for the distinct number of solutions? Briefly explain how you get the answer

3. How would you generate a recurrence formula based on your analysis in parts 1 and 2? (Hint: Deciding where to go next is in constant time (1))

4. Based on your recurrence formula, what would be the tight asymptotic bound? (Answer should be in notation)

5. Could your recurrence formula be solved by using the Master Theorem?

Since this problem has a recurrence relation, it is much easier to use recursion to solve the problem. Following are some hints for solving the problem.

1. What would be the terminal condition for your program? 2. Think about how the recurrence formula above could it help you write the recursion method.

Example Input The above table will be represented as 2d array in java and the output should be {14, 15, 16, 17, 18, 19, 20} P.S: Order is not Important There are two ways to reach 17 (1+3+5+8 and 1+2+5+9); however Bob only wants distinct possible sums, so the 17 should only appear once. This could be achieved by Hashset.

table 2: example output

7	8	9	10
4	5	6	0
2	3	0	0
1	0	0	0

please complete the java code below

main.java

package Recursion;
	import java.util.*;
	public class Main {
	public static HashSet set=new HashSet();//No need to modify this
	//You could use this to print the 2d array(No need to modify)
	public static void printArray(int[][] array) {
	for(int i=array.length-1;i>-1;i--)
	{
	for(int j=0;j
	System.out.print(array[i][j]+" ");
	}
	System.out.println();
	}
	}
	//print of all elements store in hashset with order(No need to modify)
	public static void printHashSet(HashSet set){
	ArrayListlist=new ArrayList();
	Iterator itr=set.iterator();
	while(itr.hasNext()){
	list.add((Integer) itr.next());
	}
	Collections.sort(list, Comparator.naturalOrder());
	System.out.println(Arrays.toString(list.toArray()));
	}
	//Put your code here(You could choose any return type,let method take any parameter
	// When you finish please modify the autoGrading method)
	public static void recursion(int array[][]){
	}
	//Please modify
	public static HashSet autoGrading(int array[][]){
	set=new HashSet();//No need to modify this
	recursion(array);//could modify this line to make it compatible with your own method
	//after your own method finish execution this method should return
	// the hashset that contains all possible sum
	return set;
	}
	public static void main(String[] args) {
	//Could use the main method to test
	int[][]array={{1,0,0,0},{2,3,0,0},{4,5,6,0},{7,8,9,10}};//could modify array for different test
	printArray(array);
	printHashSet(autoGrading(array));
	}
	}