Java Solution, Backtracking


  • 41

    Just try every possible number at each position...

    public class Solution {
        int count = 0;
        
        public int countArrangement(int N) {
            if (N == 0) return 0;
            helper(N, 1, new int[N + 1]);
            return count;
        }
        
        private void helper(int N, int pos, int[] used) {
            if (pos > N) {
                count++;
                return;
            }
            
            for (int i = 1; i <= N; i++) {
                if (used[i] == 0 && (i % pos == 0 || pos % i == 0)) {
                    used[i] = 1;
                    helper(N, pos + 1, used);
                    used[i] = 0;
                }
            }
        }
    }
    

  • 0
    M
    This post is deleted!

  • 3
    M

    @shawngao
    Hi ShawnGao,
    This is a great solution. How do you think in terms of coding for a backtracking problem like this. I mean I could think of the solution for this problem in which either I had to make all the permutations and then count how many satisfy the condition for which I had to use some kind of recursion. But i was not able to get the code working i.e. I can code if it is a simple recursive problem like in a binary tree finding the maxDepth, etc but when it comes to this kind of problems I have been facing difficulty implementing it or thinking about the implementation hard. How do you approach these kinds of problems? Any suggestion on implementing these problems is helpful especially in a shorter duration such as interviews?
    Thanks
    Sumanth


  • 22

    @mssumanth I would say Practice Makes Perfect.

    A general recursive template for backtracking may look like this:

       helper (parameters of given data and current recursive level) {
            // Handle base cases, i.e. the last level of recursive call
            if (level == lastLevel) {
                record result;
                return sth;
            }
            // Otherwise permute every possible value for this level.
            for (every possible value for this level) {
                helper(parameters of given data and next recursive level);
            }
            return sth;
        }
    

  • 0
    M

    @shawngao Thanks a lot @shawngao :)


  • 1
    Y

    can use bit manipulation to replace used boolean array

    public class Solution {
        public int countArrangement(int N) {
            int[] cnt = new int[1];
            int bit = 0;
            dfs(N, cnt, bit, 1);
            return cnt[0];
        }
        
        private void dfs(int N, int[] cnt, int bit, int step) {
            if (step == N + 1) { cnt[0] ++; return; }
            for (int i = 1; i<= N; i ++) {
                if (((1 << i) & bit) > 0) continue;
                if (step % i == 0 || i % step == 0)
                    dfs(N, cnt, (1 << i) | bit, step + 1);
            }
        }
    }
    

  • 1

    Great solution!

    Since N <= 15, initially I thought about simple brute force with std::next_permutation to go through every permutation of {1, 2, ..., N}, but it got TLE at input N = 12 (because I didn't realize 15! is actually in the magnitude of 10^12 :-) ).

    Basically a rewritten version in C++:

        int count = 0, used = 0, pos = 1;
        
        int countArrangement(int N) {
            for (int i = 1; i <= N && pos <= N; i++)
              if ((used & 1<<i) + (i%pos)*(pos%i) == 0)
                used ^= 1<<i, ++pos, countArrangement(N), used ^= 1<<i, --pos;
            return count += (pos > N);
        }
    

  • 6

    @mssumanth

    2 points to add to @shawngao's answer -

    1. In Leetcode, there are many backTrack problems, some of which are good starting points.
      Combination Sum, Factor Combinations, Permutations, Permutations II.
      More advanced: Evaluate Division, Word Pattern II, Remove Invalid Parentheses, Basic Calculator
    2. When solving a BT problem, pay attention to whether it's a Permutation problem, or a Combination.
      The problem here is a permutation.

  • 0
    M

    @zzhai Thanks a lot @zzhai


  • 0
    used[i] = 1;
    helper(N, pos + 1, used);
    used[i] = 0;
    

    this is awesome!

    thanks.


  • 1

    @shawngao
    in the helper function you don't have to iterate through 1 to N and use used[] array to tell a number is used or not. You can simply initialize the array to be nums[i] = i and in the helper function swap them so you just need iterate through pos to N. I think that's the standard back tracking

        private void helper(int[] nums, int start) {
            if (start == nums.length) {
                count++;
                return;
            }
            for (int i = start; i < nums.length; 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, 1);
            return count;
        }
    

  • 0

    @dreamchase said in Java Solution, Backtracking:

    @shawngao
    in the helper function you don't have to iterate through 1 to N and use used[] array to tell a number is used or not. You can simply initialize the array to be nums[i] = i and in the helper function swap them so you just need iterate through pos to N. I think that's the standard back tracking

    Great point. I was also thinking that the values which have been used before should not be put in the loop again because we started with the original order [1, 2, ..., N] and we knew exactly what values have been tested.

    Here is basically a rewritten version of your idea in C++. It speeds up from ~200ms to 60ms:

        int nums[16] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
        
        int countArrangement(int N, int s = 1) { // s: start index
          for (int i = s; i <= N; i++) 
            if ((nums[i]%s)*(s%nums[i]) == 0)
              swap(nums[i],nums[s]), countArrangement(N,s+1), swap(nums[i],nums[s]);
          return nums[0] += (s>N);
        }
    

  • 0

    @zzg_zzm
    Actually start from the back is even faster. You can look at my 6ms version :)


  • 0
    I

    @shawngao Thanks a lot for sharing your code :)


  • 0
    L

    Clear java code

    public class Solution {
        public int countArrangement(int N) {
            // arr[0] is reserved for sum
            int[] array = new int[N + 1];
            settle(N, array);
            return array[0];
        }
        
        private void settle(int n, int[] array) {
            if (n == 1) {
                // 1 could be settled anywhere, sum++
                array[0] ++;
                return;
            }
            for (int i = 1; i < array.length; i ++) {
               // check i is not occupied and fit n
                if (array[i] == 0 && (n % i == 0 || i % n == 0)) {
                    // n is settled to i
                    array[i] = n;
                   // get n - 1 settled
                    settle(n - 1, array);
                   // backtrack
                    array[i] = 0;
                }
            }
        }
        
    }
    

  • 0
    K

    @shawngao

    public class Solution {
        public int countArrangement(int n) {
            boolean[] used = new boolean[n + 1];
            return dfs(1, n, used);
        }
        
        private int dfs(int position, int n, boolean[] used) {
            if (position == (n + 1)) {
                return 1;
            }
            
            int count = 0;
            for (int test = 1; test <= n; test ++) {
                if (!used[test] && isBeautiful(position, test)) {
                    used[test] = true;
                    count += dfs(position + 1, n, used);
                    used[test] = false;
                }
            }
            
            return count;
        }
        
        private boolean isBeautiful(int position, int value) {
            return (position % value == 0) || (value % position == 0);
        }
    }
    

  • 0

    Another Java solution without global variable. Thanks for sharing!

        public int countArrangement(int N) {
            return dfs(N, new boolean[N + 1], 1);
        }
        
        private int dfs(int n, boolean[] used, int k) {
            if (k == n + 1) return 1;
            int cnt = 0;
            for (int i = 1; i <= n; i++) { // If not used and "beautiful", put number i in position k
                if (used[i] || !(i % k == 0 || k % i == 0)) continue;
                used[i] = true;
                cnt += dfs(n, used, k + 1);
                used[i] = false;
            }
            return cnt;
        }
    

  • 0
    P

    Is the time complexity O(n^n)?


  • 0

    @ParinSanghavi

    Backtracking is slow, but not as slow as O(n^n).


  • 0
    P
    This post is deleted!

Log in to reply
 

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