464. Can I Win

In the "100 game" two players take turns adding, to a running total, any integer from `1` to `10`. The player who first causes the running total to reach or exceed 100 wins.

What if we change the game so that players cannot re-use integers?

For example, two players might take turns drawing from a common pool of numbers from 1 to 15 without replacement until they reach a total >= 100.

Given two integers maxChoosableInteger and desiredTotal, return `true` if the first player to move can force a win, otherwise return `false`. Assume both players play optimally.

Example 1:

```Input: maxChoosableInteger = 10, desiredTotal = 11
Output: false
Explanation:
No matter which integer the first player choose, the first player will lose.
The first player can choose an integer from 1 up to 10.
If the first player choose 1, the second player can only choose integers from 2 up to 10.
The second player will win by choosing 10 and get a total = 11, which is >= desiredTotal.
Same with other integers chosen by the first player, the second player will always win.
```

Example 2:

```Input: maxChoosableInteger = 10, desiredTotal = 0
Output: true
```

Example 3:

```Input: maxChoosableInteger = 10, desiredTotal = 1
Output: true
```

Constraints:

• `1 <= maxChoosableInteger <= 20`
• `0 <= desiredTotal <= 300`

464. Can I Win
``````struct Solution;

use std::collections::HashMap;

impl Solution {
fn can_i_win(max_choosable_integer: i32, desired_total: i32) -> bool {
let nums: Vec<i32> = (1..=max_choosable_integer).collect();
let n = nums.len();
if desired_total > nums.iter().sum::<i32>() {
return false;
}
let mut memo: HashMap<u32, bool> = HashMap::new();
Self::dp(desired_total, (1 << n) - 1, &mut memo, &nums, n)
}

fn dp(total: i32, bitset: u32, memo: &mut HashMap<u32, bool>, nums: &[i32], n: usize) -> bool {
if let Some(&res) = memo.get(&bitset) {
return res;
}
let mut res = false;
for i in 0..n {
if res {
break;
}
if 1 << i & bitset > 0 {
if total - nums[i] <= 0 {
res = true;
}
res |= !Self::dp(total - nums[i], bitset & !(1 << i), memo, nums, n);
}
}
memo.insert(bitset, res);
res
}
}
#[test]
fn test() {
let max_choosable_integer = 10;
let desired_total = 11;
let res = false;
assert_eq!(
Solution::can_i_win(max_choosable_integer, desired_total),
res
);
let max_choosable_integer = 4;
let desired_total = 6;
let res = true;
assert_eq!(
Solution::can_i_win(max_choosable_integer, desired_total),
res
);
let max_choosable_integer = 5;
let desired_total = 50;
let res = false;
assert_eq!(
Solution::can_i_win(max_choosable_integer, desired_total),
res
);
let max_choosable_integer = 18;
let desired_total = 188;
let res = false;
assert_eq!(
Solution::can_i_win(max_choosable_integer, desired_total),
res
);
}
``````