Java

/**

 Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the ith position (1 <= i <= N) in this array:

 The number at the ith position is divisible by i.
 i is divisible by the number at the ith position.
 Now given N, how many beautiful arrangements can you construct?

 Example 1:
 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.
 Note:
 N is a positive integer and will not exceed 15.

 */

public class Beautiful_Arrangement {


    public class Solution_trim {
        int count = 0;
        public int countArrangement(int N) {
            int[] nums = new int[N];
            for (int i = 1; i <= N; i++)
                nums[i - 1] = i;
            permute(nums, 0);
            return count;
        }
        public void permute(int[] nums, int l) {
            if (l == nums.length) {
                count++;
            }
            for (int i = l; i < nums.length; i++) {
                swap(nums, i, l);

                // @note: only the current index is ok, then add it
                if (nums[l] % (l + 1) == 0 || (l + 1) % nums[l] == 0) {
                    permute(nums, l + 1);
                }
                swap(nums, i, l);
            }
        }
        public void swap(int[] nums, int x, int y) {
            int temp = nums[x];
            nums[x] = nums[y];
            nums[y] = temp;
        }
    }

    public class Solution {
        int count = 0;
        public int countArrangement(int N) {

            if (N < 0) {
                return count;
            }

            int[] nums = new int[N];
            for (int i = 1; i <= N; i++) {
                nums[i - 1] = i;
            }

            permute(nums, 0);

            return count;
        }

        public void permute(int[] nums, int l) {
            if (l == nums.length - 1) {
                isBeautiful(nums);
            }

            for (int i = l; i < nums.length; i++) {
                swap(nums, i, l);
                permute(nums, l + 1);
                swap(nums, i, l);
            }
        }

        public void swap(int[] nums, int x, int y) {
            int temp = nums[x];
            nums[x] = nums[y];
            nums[y] = temp;
        }

        private void isBeautiful (int[] nums) {
            int i;
            for (i = 1; i <= nums.length; i++) {
                if (nums[i - 1] % i != 0 && i % nums[i - 1] != 0)
                    break;
            }
            if (i == nums.length + 1) {
                count++;
            }
        }
    }

}

Java

class Solution {
    int count = 0;

    public int countArrangement(int N) {
        if (N == 0)
            return 0;
        boolean[] used = new boolean[N + 1];
        backtrack(N, 1, used);
        return count;
    }

    public void backtrack(int N, int position, boolean[] used) {
        if (position > N)
            count++;
        else {
            for (int i = 1; i <= N; i++) {
                if (!used[i] && (i % position == 0 || position % i == 0)) {
                    used[i] = true;
                    backtrack(N, position + 1, used);
                    used[i] = false;
                }
            }
        }
    }
}

All Problems

All Solutions