# Maximun distance that can be reached [duplicate]

A stone is located at the point (0,0) of an infinite grid. The stone has exactly $$n$$ possible moves, not necessarily unique, each described by a $$vector$$ of integer coordinates. The stone can make each move at most once , and the moves it makes may be arranged in any order.The goal is to reach a point as far (in the Euclidean distance) from the initial position as possible. How far can the stone be reached ? $$($$ Given that output is square of max distance $$)$$

Example : consider $$n$$ $$=$$ $$4$$ and vectrs are

$$[$$2,-2 $$]$$ ,[-2,-2],[0,2],[3,1],[-3,1]

Ans is $$26$$ Optimal way is to use vectors [0,2], [3,1], and [2,−2].or also [0,2], [−3,1], and [−2,−2].

link for vector clarity is https://ibb.co/mJByc99

• Please open this question, as the answer uses brute force (nobody uses brute force in real life) Commented May 15, 2022 at 19:40

$$(0,2) + (3,1) + (2,-2) = (0,2) + (2,-2) + (3,1) = (3,1) + (0,2) + (2,-2) = (5,1)$$
So a simple brute force method is to calculate the distance traveled for all subsets of the set of $$n$$ possible moves. There are $$2^n$$ such subsets, but you don't need to consider the empty set. So the size of your search space is actually $$2^n-1$$.