JAVA, backtracking, how to improve performance


  • 0
    Z

    The key of this solution is remove elements after calling backtrack. But contains method will slow down the program, at least I think so. Is there any way to improve it?

    public List<List<Integer>> permute(int[] num) {
        List<List<Integer>> lists = new ArrayList<List<Integer>>();
        List<Integer> list = new ArrayList<Integer>();
        backtrack(lists, list, num);
        return lists;
    }
    public void backtrack(List<List<Integer>> lists, List<Integer> list, int[] num){
        if(list.size() == num.length) {
            lists.add(new ArrayList<Integer>(list));
            return;
        }
        for(int i:num){
            if(!list.contains(i)){
                list.add(i);
                backtrack(lists, list, num);
                list.remove(Integer.valueOf(i));
            }
        }
    }

  • 0
    H

    Use a boolean array to indicate whether we have included ith element in the current list?


Log in to reply
 

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