12 ms Java Backtracking sulotion


  • 11
    I

    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;
            }
        }
    }
    

  • 5

    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.


  • 0
    I

    @ibmtp380 Nice clean Solution.. Thanks :)


  • 1
    N

    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.


  • 0
    I

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


  • 0
    N

    @ibmtp380 Thanks.


  • 0

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


  • 1
    N

    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.


  • 0
    D

    @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);
    }
    }
    }
    }


  • 0
    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);
        }
    }
    

Log in to reply
 

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