Backtracking Solution got TLE!


  • 0
    B

    Here is the solution using backtracking, But, I really think this problem shouldn't be put under the category of Backtracking, because it got TLE :

    public class Solution {
        boolean [] used = new boolean[10];
        StringBuilder builder = new StringBuilder();
        int count = 0;
        public String getPermutation(int n, int k) {
            helper(n, k, n);
            return builder.toString();
        }
        public boolean helper(int n, int k, int len){
            if(len == 0){
                ++count;
                return count == k? true:false;
            }
            for(int i = 1;i<=n;++i){
                if(used[i]) continue;
                used[i] = true;
                builder.append(i);
                if(helper(n, k, len-1)) return true;
                used[i] = false;
                builder.deleteCharAt(builder.length()-1);
            }
            return false;
        }
    }
    

  • 0

    @biwuxia Definitely you can solve it using backtracking but of course you can achieve that by iterative too.

    But your solution here is not efficient enough, try to adopt more mathematical acceleration here.


Log in to reply
 

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