Java 6ms beats 98% back tracking (swap) starting from the back


  • 22

    The back tracking start from the back so that each search won't go too deep before it fails because smaller numbers have higher chance to be divisible among themselves. Also I don't use "visited" boolean array but use swap of an array of 1~N to avoid duplication.

        private int count = 0;
        private void swap(int[] nums, int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
        private void helper(int[] nums, int start) {
            if (start == 0) {
                count++;
                return;
            }
            for (int i = start; i > 0; i--) {
                swap(nums, start, i);
                if (nums[start] % start == 0 || start % nums[start] == 0) helper(nums, start-1);
                swap(nums,i, start);
            }
        }
        public int countArrangement(int N) {
            if (N == 0) return 0;
            int[] nums = new int[N+1];
            for (int i = 0; i <= N; i++) nums[i] = i;
            helper(nums, N);
            return count;
        }
    

  • 0
    X

    Why do you judge nums[start] % start == 0 || start % nums[start] == 0?
    My code is nums[i] % nums[start] == 0 || nums[start] % nums[i] == 0,
    and I got wrong answer.


  • 1

    Because I swap the ith and the startth element before the if statement. So the ith element is now at the startth and at each step our goal is to make the startth element a beautiful arrangement.


  • 0
    X

    @dreamchase I got it !!!


  • 0
    X

    A bit improvement:

    public int countArrangement(int N) {
        return countArrangement(N, 1, new boolean[N + 1]);
    }
    
    private int countArrangement(final int N, int pos, final boolean[] used) {
        if (pos > N) return 1;
        int res = 0;
        for (int i = 1; i <= N; i++) {
            if (used[i] == false && (i % pos == 0 || pos % i == 0)) {
                used[i] = true;
                res += countArrangement(N, pos + 1, used);
                used[i] = false;
            }
        }
        return res;
    }
    

  • 1
    J

    +1 for starting from back


  • 0
    S

    is the solution based on Steinhaus–Johnson–Trotter algorithm ?


  • 0
    J

    beautiful solution!


  • 0
    R

    Hi @dreamchase , I'm not clear about the condition in

    if (nums[start] % start == 0 || start % nums[start] == 0)
    

    Why should we compare nums[start] and start? Can we do following since we set original array as nums[i] = i:

    if (i % start == 0 || start % i == 0)
    

    I tried, and it failed when N == 7.
    Can we compare nums[i] and i?
    Thanks!


Log in to reply
 

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