# 12 ms Java Backtracking sulotion

• The trick is: Arrange the values starting from the end of the array.

public class Solution {
public int countArrangement(int N) {
dfs(N, N, new boolean[N + 1]);
return count;
}

int count = 0;

void dfs(int N, int k, boolean[] visited) {
if (k == 0) {
count++;
return;
}
for (int i = 1; i <= N; i++) {
if (visited[i] || k % i != 0 && i % k != 0) {
continue;
}
visited[i] = true;
dfs(N, k - 1, visited);
visited[i] = false;
}
}
}

• You can make it a bit faster by stopping the recursion at k < 2 instead of at k == 0. No need to check whether position 1 can hold the last remaining number. It always can.

• @ibmtp380 Nice clean Solution.. Thanks :)

• Correct me if I'm wrong. This solution is faster because arranging from the end eliminates more impossible situations? Especially position 1 can hold every possible number.

• @NoAnyLove right. this reduces the number of the branches in search tree.

• @ibmtp380 Thanks.

• @NoAnyLove Still not get why it is faster, can you help elaborate more why it is faster?

• Hi @pinkfloyda ,

@StefanPochmann explained this quite well at https://discuss.leetcode.com/topic/79968/easy-python-230ms

Let's have a short example, say N=5. If we start from beginning, since 1st position can hold any number, we would have to call dfs 5 times at the 1st level of our recursion. You can image it as a tree with 5 branches, and each branch will have more calls recursively.

But if we start from end, the 5th position can only hold 1 or 5, it would be a tree with only 2 branches. It may be helpful if you could draw a call graph of an tiny example N=3.

• @ibmtp380

Could you please help me to figure out what mistake i am making. Here is my Code:-

public void combination(int[] arr,int start,int end)
{
if(start>=end)
{
return;
}
if(start<end)
{
printArray(arr);
count++;
}
for(int i=start;i<end;i++)
{
for(int j=i+1;j<end;j++)
{
if((arr[i]%(j+1)==0 || (j+1)%arr[i]==0) &&(arr[j]%(i+1)==0 || (i+1)%arr[j]==0))
{
//System.out.println(arr[i]+"---->"+(j+1));
//System.out.println((j+1)+"---->"+arr[i]);
swap(arr,i,j);
combination(arr,i+1,end);
swap(arr,i,j);
}
}
}
}

• Here is my implementation, using bit instead of array for speed up

public class Solution {
private int helper(int ind, int max, int taken) {
if (ind < 2) return 1;
int res = 0;
for (int i = max; i >= 1; i--) {
if ((taken & (1 << i)) == 0 && (i % ind == 0 || ind % i == 0)) {
res += helper(ind - 1, max, taken ^ (1 << i));
}
}
return res;
}
public int countArrangement(int N) {
return helper(N, N, 0);
}
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.