If either coordinate exceeds the target (x > tx or y > ty), stop exploring that path (prune the search tree).

Visualization

The process can be visualized as a binary tree, where each node represents a possible state (x, y), and each branch corresponds to one of the two allowed moves.

---
title: sx=1, sy=1, tx=3, ty=5
---

graph TD
	A(1,1)
	B(2,1)
	C(1,2)
	D(3,1)
	E(2,3)
	F(1,3)
	G(3,2)
	H(2,5)
	I(1,5)
	J(5,1)
	K(3,5):::green
	L(5,2)

	A -- "+y" --> B
	A -- "+x" --> C
	B -- "+y" --> D
	B -- "+x" --> E
	C -- "+y" --> F
	C -- "+x" --> G
	E -- "+y" --> H
	F -- "+x" --> I
	D -- "+y" --> J
	G -- "+y" --> K
	G -- "+x" --> L

classDef green fill:#3CB371,stroke:#000,stroke-width:1px,color:#fff;

Code

[{"language":"C++","code":"class Solution {\npublic:\n\tbool reachingPoints(int sx, int sy, int tx, int ty) {\n\t\tif (sx == tx && sy == ty) return true;\n\t\tif (sx > tx || sy > ty) return false;\n\t\treturn reachingPoints(sx + sy, sy, tx, ty) || reachingPoints(sx, sx + sy, tx, ty);\n\t}\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">\tbool</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> reachingPoints</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> sx</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> sy</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> tx</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> ty</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">\t\tif</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> (sx </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">==</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> tx </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x26;&#x26;</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> sy </span><span sty

Related Tags