Help with recursive backtracking in Java

[joerocket23]

Hello there,

I am working on a programming assignment that has a question that I am thoroughly stuck on. The assignment is full of problems that we must solve recursively, and this is the one I would really appreciate some help on.

I have a method that creates a number of teams that are as even as possible based on the skill of the players. My method is passed the number of teams I must make, and an array of ints that represents the players "skill". It is called like so:

int[] abilities = {1, 2, 3, 4, 5, 6, 7};
minDifference(3, abilities)

An example of the fairest teams given those parameters could be:

Team 1: 1 + 3 + 6 = 10
Team 2: 2 + 7 = 9
Team 3: 4 + 5 = 9

In which case my method would return 1, the amount of skills points that the teams are even within.

I am stuck on this because I can't think of what the base case should be. Once I understand this, I will be on my way to solving the rest of the problem.

What would you consider the base case in this problem?

Thanks in advance!

 

[eon]

wouldnt the base case be when all available values are taken while the root of the tree is no players on any team?
bare with me here, this is just me thinking aloud trying to brush up on my algorithm stuff:

i think this is np complete so you will have to iterate through every possibility. You take a given player at each level of the recursive tree and branch it out to each possibility by adding that player to each team.
So for your example your tree will have 6 levels from the root as you add a player to a team on each level.

Also having to deal with a variable number of teams kinda makes this needlessly messy I think, forcing you to loop unless ofcourse theres a better way.

EDIT: *embarrassingly incorrect pseudo code removed until further notice*
DOUBLE EDIT: hmm maybe this does kinda work?
get_min(team_list, player_stack, num_teams)
{
if(player_stack.empty())
return team_list.difference() //function to calculate skill difference
temp= player_stack.pop()
for(i -> num_teams)
{
team_list.add(temp)
temp_min_array = get_min(team_list, player_stack, num_teams)
team_list.remove(temp)
}
return min(temp_min_array) //returns min value from array
}

again I kinda rushed through this so it may not be complete & accurate but hopefully you get the idea

 

[joerocket23]

Thanks a lot! This got me in the right direction.