Leetcode - 526. Beautiful Arrang

Input:2

Output:2

Explanation:

The first beautiful arrangement is [1, 2]:

Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1).

Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2).

The second beautiful arrangement is [2, 1]:

Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1).

Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.

question

解法：backtracking

逻辑：

假设我们有个N长的array，我们在array的第一位测试数字1能不能满足条件，如果能满足，我们去到array的下一个位置，测试数字2能不能fit，当1～N全部测试完之后，根据backtraking的特性回弹回：

for i in range(N):

    if the i satisfy requirement , put i on current posistion

    then we call recusion to the 

    foo(currentposn+1,arr)

    free the arr[i] for the future use 

reference：

https://discuss.leetcode.com/topic/79916/java-solution-backtracking/2