public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
boolean candidates[] = new boolean[maxChoosableInteger];
for (int i = 0; i < candidates.length; ++i) {
candidates[i] = true;
}
return canWinHelper(candidates, desiredTotal);
}
private boolean canWinHelper(boolean candidates[], int total) {
if (total <= 0) {
return false;
}
boolean result = false;
for (int i = 0; i < candidates.length; ++i) {
// I pick, just win one
if (candidates[i]) {
candidates[i] = false;
int curTotal = total - i - 1;
if(curTotal == 0) {
System.out.println("return");
return true;
}
// the other player pick: any possibility
// need to win all these
boolean cur = true;
for(int j = 0; j < candidates.length; ++j) {
if(candidates[j]) {
candidates[j] = false;
cur = cur && canWinHelper(candidates, curTotal - j - 1);
candidates[j] = true;
}
}
result = result || cur;
candidates[i] = true;
}
}
return result;
}
Thursday, May 28, 2015
L Question: WinGame
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment