Simple Java Solution beats 92% Using backtracking


  • 0
    S
        public String getPermutation(int n, int k) {
            StringBuilder sb = new StringBuilder();
            if ( k > factorial(n) || k <= 0) return null;
            boolean[] used = new boolean[n + 1];
            backtrack(sb, k, n, used);
            return sb.toString();
        }
        private void backtrack(StringBuilder sb, int k, int n, boolean[] used) {
            if (sb.length() == n) return;
            else {
                int times = 1;
                int factorial = factorial(n - 1 -sb.length());
                for (int i = 1; i <= n; i++) {
                    if (used[i]) continue;
                    else {
                        if (k <= times * factorial) {
                            sb.append(i);
                            used[i] = true;
                            backtrack(sb,k - (times - 1) * factorial,n,used);
                        }
                        else times++;
                    }
                }
            }
        }
    
        private int factorial (int n) {
            int res = 1;
            while (n > 1) {
                res *= n;
                n--;
            }
            return res;
        }

Log in to reply
 

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