A good way into this one is to ask: what do we need to remember so we never redo work blindly? For 464. Can I Win, the solution in this repository is mainly a DFS + memoization solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: DFS + memoization, dynamic programming.
The notes already sitting in the source point us in the right direction:
- brute force
- https://leetcode.com/problems/can-i-win/discuss/155321/From-Brute-Force-to-Top-down-DP
- TLE
- 5 / 54 test cases passed.
Guide
When?
This is the kind of solution you want when the problem has structure hiding inside a messy-looking input. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are canWin, canIWin, choosable.
Guide
Why?
The win comes from making each line carry responsibility: store the useful state, discard the rest, keep moving.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//brute force
02//https://leetcode.com/problems/can-i-win/discuss/155321/From-Brute-Force-to-Top-down-DP
03//TLE
04//5 / 54 test cases passed.
05class Solution {
06public:
07 bool canWin(vector<bool>& choosable, int target){
08 if(none_of(choosable.begin(), choosable.end(),
09 [](const bool b){return b;})){
10 return false;
11 }
12
13 if(target <= 0){
14 return false;
15 }
16
17 int maxChoosable;
18 for(int i = choosable.size()-1; i >= 1; i--){
19 if(choosable[i]){
20 maxChoosable = i;
21 break;
22 }
23 }
24
25 if(target <= maxChoosable){
26 //we can go to the number >= target
27 return true;
28 }
29
30 //once we can make the next player lose, we win
31 for(int i = 1; i < choosable.size(); i++){
32 if(choosable[i]){
33 bool nextCanWin;
34 choosable[i] = false;
35 nextCanWin = canWin(choosable, target-i);
36 choosable[i] = true;
37 if(!nextCanWin) return true;
38 }
39 }
40 //the next player will win anyway
41 return false;
42 }
43
44 bool canIWin(int maxChoosableInteger, int desiredTotal) {
45 if(desiredTotal <= maxChoosableInteger){
46 return true;
47 }
48
49 if((1+maxChoosableInteger)*maxChoosableInteger/2 < desiredTotal){
50 return false;
51 }
52
53 //0 for padding
54 vector<bool> choosable(maxChoosableInteger+1, true);
55 return canWin(choosable, desiredTotal);
56 }
57};
58
59//top-down DP
60//https://leetcode.com/problems/can-i-win/discuss/155321/From-Brute-Force-to-Top-down-DP
61//Runtime: 872 ms, faster than 5.08% of C++ online submissions for Can I Win.
62//Memory Usage: 71.4 MB, less than 12.41% of C++ online submissions for Can I Win.
63class Solution {
64public:
65 unordered_map<string, bool> memo;
66
67 bool canWin(vector<bool>& choosable, int target){
68 if(none_of(choosable.begin(), choosable.end(),
69 [](const bool b){return b;})){
70 return false;
71 }
72
73 if(target <= 0){
74 return false;
75 }
76
77 int maxChoosable;
78 //choosable[0] is just for padding, so we end at 1!
79 for(int i = choosable.size()-1; i >= 1; i--){
80 if(choosable[i]){
81 maxChoosable = i;
82 break;
83 }
84 }
85
86 if(target <= maxChoosable){
87 //we can go to the number >= target
88 return true;
89 }
90
91 /*
92 don't need to track "target",
93 since target can be calculated from "desiredTotal" and
94 current "choosable"!
95 */
96 string key = string(choosable.begin(), choosable.end());
97
98 if(memo.find(key) != memo.end()){
99 return memo[key];
100 }
101
102 //once we can make the next player lose, we win
103 //choosable[0] is just for padding, so we start from 1!
104 for(int i = 1; i < choosable.size(); i++){
105 if(choosable[i]){
106 bool nextCanWin;
107 choosable[i] = false;
108 nextCanWin = canWin(choosable, target-i);
109 choosable[i] = true;
110 if(!nextCanWin) return memo[key] = true;
111 }
112 }
113 //the next player will win anyway
114 return memo[key] = false;
115 }
116
117 bool canIWin(int maxChoosableInteger, int desiredTotal) {
118 if(desiredTotal <= maxChoosableInteger){
119 return true;
120 }
121
122 if((1+maxChoosableInteger)*maxChoosableInteger/2 < desiredTotal){
123 return false;
124 }
125
126 //0 for padding
127 vector<bool> choosable(maxChoosableInteger+1, true);
128 return canWin(choosable, desiredTotal);
129 }
130};
131
132//top-bottom dp, use vector<int>
133//https://leetcode.com/problems/can-i-win/discuss/95320/Clean-C%2B%2B-beat-98.4-DFS-with-early-termination-check-(detailed-explanation)
134//Runtime: 48 ms, faster than 63.89% of C++ online submissions for Can I Win.
135//Memory Usage: 149.1 MB, less than 7.81% of C++ online submissions for Can I Win.
136class Solution {
137public:
138 vector<int> memo;
139 // int memo[1<<20];
140
141 int canWin(int maxChoosableInteger, int state, int target){
142 /*
143 state: can be thought as bits s.t.
144 ith bit represents integer i+1 is chosen or not
145 */
146 // cout << state << endl;
147 if(memo[state] != 0){
148 return memo[state] == 1;
149 }
150
151 if(target <= 0){
152 return false;
153 }
154
155 //once we can make the next player lose, we win
156 /*
157 i's range is [0, maxChoosableInteger-1],
158 but it represents for the numbers to be chosen: [1, maxChoosableInteger]
159 */
160 for(int i = 0; i < maxChoosableInteger; i++){
161 /*
162 state&(1<<i): ith bit of state, represents for i+1 is chosen or not
163 state|(1<<i): saying that ith bit is already chosen
164 */
165 if(!(state&(1<<i)) && !canWin(maxChoosableInteger, state|(1<<i), target-(i+1))){
166 memo[state] = 1;
167 return true;
168 }
169 }
170 //the next player will win anyway
171 memo[state] = -1;
172 return false;
173 }
174
175 bool canIWin(int maxChoosableInteger, int desiredTotal) {
176 if(desiredTotal <= maxChoosableInteger){
177 return true;
178 }
179
180 int sum = (1+maxChoosableInteger)*maxChoosableInteger/2;
181
182 /*
183 can't make up desiredTotal using [1, maxChoosableInteger],
184 so neither can win
185 */
186 if(sum < desiredTotal){
187 return false;
188 }else if(sum == desiredTotal){
189 /*
190 we will reach desiredTotal at last step,
191 so the player who choose the last integer will win,
192 i.e. when maxChoosableInteger is odd, 1st player will win
193 */
194 return maxChoosableInteger % 2;
195 }
196
197 memo = vector<int>(1<<20, 0);
198 return canWin(maxChoosableInteger, 0, desiredTotal);
199 }
200};
201
202//top-bottom dp, use int array
203//Runtime: 16 ms, faster than 90.35% of C++ online submissions for Can I Win.
204//Memory Usage: 10.5 MB, less than 93.88% of C++ online submissions for Can I Win.
205class Solution {
206public:
207 // vector<int> memo;
208 int memo[1<<20];
209
210 int canWin(int maxChoosableInteger, int state, int target){
211 /*
212 state: can be thought as bits s.t.
213 ith bit represents integer i+1 is chosen or not
214 */
215 // cout << state << endl;
216 if(memo[state] != 0){
217 return memo[state] == 1;
218 }
219
220 if(target <= 0){
221 return false;
222 }
223
224 //once we can make the next player lose, we win
225 /*
226 i's range is [0, maxChoosableInteger-1],
227 but it represents for the numbers to be chosen: [1, maxChoosableInteger]
228 */
229 for(int i = 0; i < maxChoosableInteger; i++){
230 /*
231 state&(1<<i): ith bit of state, represents for i+1 is chosen or not
232 state|(1<<i): saying that ith bit is already chosen
233 */
234 if(!(state&(1<<i)) && !canWin(maxChoosableInteger, state|(1<<i), target-(i+1))){
235 memo[state] = 1;
236 return true;
237 }
238 }
239 //the next player will win anyway
240 memo[state] = -1;
241 return false;
242 }
243
244 bool canIWin(int maxChoosableInteger, int desiredTotal) {
245 if(desiredTotal <= maxChoosableInteger){
246 return true;
247 }
248
249 int sum = (1+maxChoosableInteger)*maxChoosableInteger/2;
250
251 /*
252 can't make up desiredTotal using [1, maxChoosableInteger],
253 so neither can win
254 */
255 if(sum < desiredTotal){
256 return false;
257 }else if(sum == desiredTotal){
258 /*
259 we will reach desiredTotal at last step,
260 so the player who choose the last integer will win,
261 i.e. when maxChoosableInteger is odd, 1st player will win
262 */
263 return maxChoosableInteger % 2;
264 }
265
266 // memo = vector<int>(1<<20, 0);
267 return canWin(maxChoosableInteger, 0, desiredTotal);
268 }
269};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.