Thursday, May 28, 2015

L Question: WinGame

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;
 }

No comments:

Post a Comment